HardNo. 1548LeetCode Premium
The Most Similar Path in a Graph — LeetCode 1548 Python Solution
- Pattern
- Depth-First Search
- Topics
- Graph, Dynamic Programming
- Reading time
- 5 min
- Source
- leetcode.com
The problem
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 three upper-case English letters given in the string array names.
Example
- 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.
Python solution
class Solution:
def mostSimilar(
self, n: int, roads: List[List[int]], names: List[str], targetPath: List[str]
) -> List[int]:
g = [[] for _ in range(n)]
for a, b in roads:
g[a].append(b)
g[b].append(a)
m = len(targetPath)
f = [[inf] * n for _ in range(m)]
pre = [[-1] * n for _ in range(m)]
for j, s in enumerate(names):
f[0][j] = targetPath[0] != s
for i in range(1, m):
for j in range(n):
for k in g[j]:
if (t := f[i - 1][k] + (targetPath[i] != names[j])) < f[i][j]:
f[i][j] = t
pre[i][j] = k
k = 0
mi = inf
for j in range(n):
if f[-1][j] < mi:
mi = f[-1][j]
k = j
ans = [0] * m
for i in range(m - 1, -1, -1):
ans[i] = k
k = pre[i][k]
return ansComplexity
- Time
- O(m × n2)
- Space · auxiliary
- O(m × n)
Pattern: Depth-First Search
Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 1548. The Most Similar Path in a Graph is filed here because LeetCode tags it Graph, which is the vocabulary this hub collects.
The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0329 | Longest Increasing Path in a Matrix | Hard |
| 0787 | Cheapest Flights Within K Stops | Medium |
| 0834 | Sum of Distances in Tree | Hard |
| 0847 | Shortest Path Visiting All Nodes | Hard |
| 0913 | Cat and Mouse | Hard |
| 1334 | Find the City With the Smallest Number of Neighbors at a Threshold Distance | Medium |
Frequently asked questions
- How hard is LeetCode 1548. The Most Similar Path in a Graph?
LeetCode 1548. The Most Similar Path in a Graph is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1548. The Most Similar Path in a Graph?
The Python solution on this page runs in O(m × n2).
- What is the space complexity of LeetCode 1548. The Most Similar Path in a Graph?
The Python solution on this page uses O(m × n) auxiliary space.
- What topics does LeetCode 1548. The Most Similar Path in a Graph cover?
LeetCode 1548. The Most Similar Path in a Graph is tagged Graph and Dynamic Programming on LeetCode.
- Is LeetCode 1548. The Most Similar Path in a Graph a premium problem?
Yes. LeetCode 1548. The Most Similar Path in a Graph is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.