LC-0847 Hard LeetCode

847. Shortest Path Visiting All Nodes

Dynamic Programming Bit Manipulation Breadth-First Search Graph Bitmask

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 65% Topics: Dynamic Programming, Bit Manipulation, Breadth-First Search, Graph, Bitmask

Reading material

1-D Dynamic Programming 16 min Bit Manipulation 10 min Trees & Traversals 18 min

Reference solution (spoiler · python)

# Time:  O(n * 2^n)
# Space: O(n * 2^n)

import collections


class Solution(object):
    def shortestPathLength(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: int
        """
        dp = [[float("inf")]*(len(graph))
              for _ in xrange(1 << len(graph))]
        q = collections.deque()
        for i in xrange(len(graph)):
            dp[1 << i][i] = 0
            q.append((1 << i, i))
        while q:
            state, node = q.popleft()
            steps = dp[state][node]
            for nei in graph[node]:
                new_state = state | (1 << nei)
                if dp[new_state][nei] == float("inf"):
                    dp[new_state][nei] = steps+1
                    q.append((new_state, nei))
        return min(dp[-1])

Solution from kamyu104/LeetCode-Solutions · MIT