本文共 3863 字，大约阅读时间需要 12 分钟。

1. 题目

We have n cities and m bi-directional roads where roads[i] = [ai, bi] connects city ai with city bi. Each city has a name consisting of exactly 3 upper-case English letters given in the string array names. Starting at any city x, you can reach any city y where y != x (i.e. the cities and the roads are forming an undirected connected graph).

You will be given a string array targetPath. You should find a path in the graph of the same length and with the minimum edit distance to targetPath.

You need to return the order of the nodes in the path with the minimum edit distance, The path should be of the same length of targetPath and should be valid (i.e. there should be a direct road between ans[i] and ans[i + 1]). If there are multiple answers return any one of them.

The edit distance is defined as follows:

Follow-up: If each node can be visited only once in the path, What should you change in your solution?

Example 1:

Input: n = 5, roads = [[0,2],[0,3],[1,2],[1,3],[1,4],[2,4]], names = ["ATL","PEK","LAX","DXB","HND"], targetPath = ["ATL","DXB","HND","LAX"]Output: [0,2,4,2]Explanation: [0,2,4,2], [0,3,0,2] and [0,3,1,2] are accepted answers.[0,2,4,2] is equivalent to ["ATL","LAX","HND","LAX"] which has edit distance = 1 with targetPath.[0,3,0,2] is equivalent to ["ATL","DXB","ATL","LAX"] which has edit distance = 1 with targetPath.[0,3,1,2] is equivalent to ["ATL","DXB","PEK","LAX"] which has edit distance = 1 with targetPath.

Example 2:

Input: n = 4, roads = [[1,0],[2,0],[3,0],[2,1],[3,1],[3,2]], names = ["ATL","PEK","LAX","DXB"], targetPath = ["ABC","DEF","GHI","JKL","MNO","PQR","STU","VWX"]Output: [0,1,0,1,0,1,0,1]Explanation: Any path in this graph has edit distance = 8 with targetPath.

Example 3:

Input: n = 6, roads = [[0,1],[1,2],[2,3],[3,4],[4,5]], names = ["ATL","PEK","LAX","ATL","DXB","HND"], targetPath = ["ATL","DXB","HND","DXB","ATL","LAX","PEK"]Output: [3,4,5,4,3,2,1]Explanation: [3,4,5,4,3,2,1] is the only path with edit distance = 0 with targetPath.It's equivalent to ["ATL","DXB","HND","DXB","ATL","LAX","PEK"] Constraints:2 <= n <= 100m == roads.lengthn - 1 <= m <= (n * (n - 1) / 2)0 <= ai, bi <= n - 1ai != bi The graph is guaranteed to be connected and each pair of nodes may have at most one direct road.names.length == nnames[i].length == 3names[i] consists of upper-case English letters.1 <= targetPath.length <= 100targetPath[i].length == 3targetPath[i] consists of upper-case English letters.

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/the-most-similar-path-in-a-graph

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

class Solution {
   public:    vector
   
     mostSimilar(int n, vector
    
     
      >& roads, vector
      
       & names, vector
       
        & targetPath) {
           vector
        
         
          > g(n); for(auto& r : roads) { g[r[0]].push_back(r[1]); g[r[1]].push_back(r[0]); }//建图 int len = targetPath.size(); vector
          
           
            > dp(len, vector
            
             (n, INT_MAX)); //走完 ？target后的 在城市 ni 的最小编辑距离 vector
             
              
               > path1(n);//n个城市作为结束的最佳路线 vector
               
                
                 > path2(n);//存储下一个状态的路径 for(int i = 0; i < n; ++i)//初始化 { dp[0][i] = (names[i] != targetPath[0]); path1[i].push_back(i); } int mindis = INT_MAX, minidx = -1; for(int k = 1; k < len; ++k) { //样本维度 for(int i = 0; i < n; ++i) { //前一个城市 if(dp[k-1][i] == INT_MAX) continue; for(int j : g[i]) { //下一个相连的城市 if(dp[k][j] > dp[k-1][i]+(names[j]!=targetPath[k])) { dp[k][j] = dp[k-1][i]+(names[j]!=targetPath[k]); path2[j] = path1[i]; path2[j].push_back(j); } } } swap(path1, path2);//滚动数组，更新当前的最佳路径至path1 } for(int i = 0; i < n; i++) { if(mindis > dp[len-1][i]) { mindis = dp[len-1][i]; minidx = i; } }//取编辑距离最小的城市编号 return path1[minidx];//返回路径 }};
                
               
              
             
            
           
          
         
        
       
      
     
    
   

1260 ms 109.6 MB

我的CSDN

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

转载地址：https://michael.blog.csdn.net/article/details/107983113 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！