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 \times n^2).

What is the space complexity of LeetCode 1548. The Most Similar Path in a Graph?

The Python solution on this page uses O(m \times 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.

The Most Similar Path in a Graph — LeetCode 1548 Python Solution

HardLeetCode PremiumGraphDynamic Programming

Problem: #1548
Pattern: Depth-First Search
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

Python

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 ans

Complexity

Measure	Complexity
Time	O(m \times n^2)
Space	O(m \times n) auxiliary

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.

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 \times n^2).
What is the space complexity of LeetCode 1548. The Most Similar Path in a Graph?: The Python solution on this page uses O(m \times 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.