# 1548. The Most Similar Path in a Graph¶

• Time: $O(n^2 \cdot |\texttt{targetPath}|)$
• Space: $O(n^2 + n \cdot |\texttt{targetPath}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 class Solution { public: vector mostSimilar(int n, vector>& roads, vector& names, vector& targetPath) { this->names = names; this->targetPath = targetPath; // cost[i][j] := the minimum cost to start from names[i] in path[j] this->cost.resize(names.size(), vector(targetPath.size(), -1)); // next[i][j] := the best next of names[i] in path[j] this->next.resize(names.size(), vector(targetPath.size())); this->graph.resize(n); for (const vector& road : roads) { graph[road[0]].push_back(road[1]); graph[road[1]].push_back(road[0]); } int minDist = INT_MAX; int start = 0; for (int i = 0; i < n; ++i) { const int dist = dfs(i, 0); if (dist < minDist) { minDist = dist; start = i; } } vector ans; while (ans.size() < targetPath.size()) { ans.push_back(start); start = next[start][ans.size() - 1]; } return ans; } private: vector names; vector targetPath; vector> cost; vector> next; vector> graph; int dfs(int nameIndex, int pathIndex) { if (cost[nameIndex][pathIndex] != -1) return cost[nameIndex][pathIndex]; const int editDist = names[nameIndex] != targetPath[pathIndex]; if (pathIndex == targetPath.size() - 1) return editDist; int minDist = INT_MAX; for (const int v : graph[nameIndex]) { const int dist = dfs(v, pathIndex + 1); if (dist < minDist) { minDist = dist; next[nameIndex][pathIndex] = v; } } return cost[nameIndex][pathIndex] = editDist + minDist; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 class Solution { public List mostSimilar(int n, int[][] roads, String[] names, String[] targetPath) { this.names = names; this.targetPath = targetPath; // cost[i][j] := the minimum cost to start from names[i] in path[j] this.cost = new int[names.length][targetPath.length]; // next[i][j] := the best next of names[i] in path[j] this.next = new int[names.length][targetPath.length]; this.graph = new List[n]; Arrays.stream(cost).forEach(a -> Arrays.fill(a, -1)); for (int i = 0; i < n; ++i) graph[i] = new ArrayList<>(); for (int[] road : roads) { graph[road[0]].add(road[1]); graph[road[1]].add(road[0]); } int minDist = Integer.MAX_VALUE; int start = 0; // Start from different names for (int i = 0; i < names.length; ++i) { final int dist = dfs(i, 0); if (dist < minDist) { minDist = dist; start = i; } } List ans = new ArrayList<>(); while (ans.size() < targetPath.length) { ans.add(start); start = next[start][ans.size() - 1]; } return ans; } private String[] names; private String[] targetPath; private int[][] cost; private int[][] next; private List[] graph; private int dfs(int nameIndex, int pathIndex) { if (cost[nameIndex][pathIndex] != -1) return cost[nameIndex][pathIndex]; final int editDist = names[nameIndex].equals(targetPath[pathIndex]) ? 0 : 1; if (pathIndex == targetPath.length - 1) return editDist; int minDist = Integer.MAX_VALUE; for (final int v : graph[nameIndex]) { final int dist = dfs(v, pathIndex + 1); if (dist < minDist) { minDist = dist; next[nameIndex][pathIndex] = v; } } return cost[nameIndex][pathIndex] = editDist + minDist; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 class Solution: def mostSimilar(self, n: int, roads: List[List[int]], names: List[str], targetPath: List[str]) -> List[int]: # cost[i][j] := the minimum cost to start from names[i] in path[j] cost = [[-1] * len(targetPath) for _ in range(len(names))] # next[i][j] := the best next of names[i] in path[j] next = [[0] * len(targetPath) for _ in range(len(names))] graph = [[] for _ in range(n)] for u, v in roads: graph[u].append(v) graph[v].append(u) minDist = math.inf start = 0 def dfs(nameIndex: int, pathIndex: int) -> int: if cost[nameIndex][pathIndex] != -1: return cost[nameIndex][pathIndex] editDist = names[nameIndex] != targetPath[pathIndex] if pathIndex == len(targetPath) - 1: return editDist minDist = math.inf for v in graph[nameIndex]: dist = dfs(v, pathIndex + 1) if dist < minDist: minDist = dist next[nameIndex][pathIndex] = v cost[nameIndex][pathIndex] = editDist + minDist return editDist + minDist for i in range(n): dist = dfs(i, 0) if dist < minDist: minDist = dist start = i ans = [] while len(ans) < len(targetPath): ans.append(start) start = next[start][len(ans) - 1] return ans