Mistakes by myself

class Solution:
    def alphabetBoardPath(self, target: str) -> str:
        R, C =5, 5
        current = [0, 0]
        solution = ''
        moving_patterns = [['D', 'U'], ['R', 'L']]
        for c in target:
            c_code = ord(c)-97
            target_pos = [c_code//5, c_code%5]
            if c!= 'z':
                for i in [0, 1]:
                    if target_pos[i] == current[i]:
                        pass
                    else:
                        if target_pos[i]>current[i]:
                            moving = moving_patterns[i][0]
                        else:
                            moving = moving_patterns[i][1]
                        solution += moving*abs(target_pos[i]-current[i])
                solution += '!'
                current = target_pos[:]
            else:
                for i in [1, 0]:
                    if target_pos[i] == current[i]:
                        pass
                    else:
                        if target_pos[i]>current[i]:
                            moving = moving_patterns[i][0]
                        else:
                            moving = moving_patterns[i][1]
                        solution += moving*abs(target_pos[i]-current[i])
                solution += '!'
                current = target_pos[:]
        return solution

797. All Paths From Source to Target

https://leetcode.com/problems/all-paths-from-source-to-target/

My solution is below

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        self.res = []
        N = len(graph)
        def dfs(node, i):
            open_list = [(node,[[i]])]
            if node==N-1:self.res += [[i]]
            while open_list:
                node, path= open_list.pop()
                for nxt_node in graph[node]:
                    new_path = [p+[nxt_node] for p in path]
                    if nxt_node == N-1:
                        self.res += new_path
                        continue
                    open_list.append((nxt_node, new_path))
        dfs(0, 0)
        return self.res

If I change self.res to res, I got an error. Finally, I realize

res += [] operation will generate a new variable named res. In this case, we need define another variable. However, if we use res.append, we are using the old object, and we will have no error.

The following code also works.

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        res = []
        N = len(graph)
        def dfs(node, i):
            open_list = [(node,[[i]])]
            if node==N-1:res.append([i])
            while open_list:
                node, path= open_list.pop()
                for nxt_node in graph[node]:
                    new_path = [p+[nxt_node] for p in path]
                    if nxt_node == N-1:
                        res.extend(new_path)
                        continue
                    open_list.append((nxt_node, new_path))
        dfs(0, 0)
        return res

Related to heapq

Dijkstra Python - LeetCode Discuss

import heapq
class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        cost = [[float('inf')]*n for _ in range(n)]
        graph = collections.defaultdict(list)
        for a,b,c in edges:
            cost[a][b]=cost[b][a]=c
            graph[a].append(b)
            graph[b].append(a)
            
        def dijkstra(i):
            dis = [float('inf')]*n
            dis[i], pq =0, [(0, i)]
            heapq.heapify(pq)
            while pq:
                d, i = heapq.heappop(pq)
                if d> dis[i]:continue
                for j in graph[i]:
                    this_cost = d+cost[i][j]
                    if this_cost<dis[j]:
                        dis[j] = this_cost
                        heapq.heappush(pq, (this_cost, j))
            return sum(d<=distanceThreshold for d in dis)-1
        res = {dijkstra(i):i for i in range(n)}
        return res[min(res)]

I made a mistake by

pq=[(0,i)]
heapq.heapify(pq)

to

pq=heapq.heapify([0,i])

The wrong one pq will be None.