LC: 1548. The Most Similar Path in a Graph
https://leetcode.com/problems/the-most-similar-path-in-a-graph/
1548. The Most Similar Path in a Graph
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:
Example 2:
Example 3:
Constraints:
2 <= n <= 100m == roads.lengthn - 1 <= m <= (n * (n - 1) / 2)0 <= ai, bi <= n - 1ai != biThe 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.There can be two cities with the same name.
1 <= targetPath.length <= 100targetPath[i].length == 3targetPath[i]consists of upper-case English letters.
1548. The Most Similar Path in a Graph:
The Essence:
Die Editierdistanz bedeutet hier, wie viele Indizes einen unterschiedlichen Element haben, wenn sie mit dem Eingabe-Array verglichen werden. Aus dem Array roads kann man einen Graph bilden und ihn traversieren, um den Pfad mit niedrigster Editierdistanz zu finden.
Details:
Dafür kann man eine Deque verwenden, die die besten Pfade am Anfang hat und die Schlechtesten am Ende, wie eine Prioritätswarteschlange. Man kann außerdem eine Lösung durch dynamische Programmierung implementieren.
Solution(s) and Futher Explanation:
For detailed explanation and implementations for both approaches:
Default Code:
Last updated