# Hard Graph

`from collections import dequeclass Solution:    def reachableNodes(self, edges: List[List[int]], M: int, N: int) -> int:        edg = {}        graph = collections.defaultdict(list)        dp = collections.defaultdict(int)        for a,b,n in edges:            graph[a].append(b)            graph[b].append(a)            edg[(a,b)] = n            edg[(b,a)] = n        def bfs():            Q = deque([(0, 0)])            seen = collections.defaultdict(lambda: float('inf'))            seen[0] = 0            while Q:                i, d = Q.popleft()                for j in graph[i]:                    n = edg[(i,j)]                    if d+n+1<=M:                        dp[(i,j)] = n                        if seen[j] >d+n+1:                            seen[j] = d+n+1                            Q.append((j, d+n+1))                    else:                        dp[(i,j)] = max(M-d, dp[(i,j)])            return seen        seen = bfs()        res = len(seen.keys())        return res+sum(min(n, dp[(a,b)]+dp[(b,a)]) for a, b, n in edges)`

# 864. Shortest Path to Get All Keys

`class Solution:    def shortestPathAllKeys(self, grid: List[str]) -> int:        R, C = len(grid), len(grid[0])        ii, jj =0 ,0         target = 0        for i in range(R):            for j in range(C):                if grid[i][j]=='@':                    ii, jj = i, j                if grid[i][j].islower():                    target+=1        def bfs(i, j):            from collections import deque            Q = deque([(i,j, 0 ,set())])            seen = {(i,j,tuple(sorted(set())))}            while Q:                i,j, d, s = Q.popleft()                for di, dj in [(0,1),(1,0),(0,-1),(-1,0)]:                    r, c = i+di, j+dj                    if 0<=r<R and 0<=c<C:                        if grid[r][c].islower():                            #s1 = s                            s1 =  s.copy()                            s1.add(grid[r][c])                            if len(s1)==target:return d+1                            tuple_s = tuple(sorted(set(s1)))                            if (r,c,tuple_s) not in seen:                                seen.add((r,c,tuple_s))                                Q.append((r,c, d+1,s1))                        elif grid[r][c].isupper():                            if grid[r][c].lower() in s:                                tuple_s = tuple(sorted(set(s)))                                if (r,c,tuple_s) not in seen:                                    seen.add((r,c,tuple_s))                                    Q.append((r,c,  d+1, s))                        elif grid[r][c]!='#':                            tuple_s = tuple(sorted(set(s)))                            if (r,c,tuple_s) not in seen:                                seen.add((r,c,tuple_s))                                Q.append((r,c, d+1, s))            return -1        return bfs(ii,jj)`
`s1 = s.copy()`

# 854. K-Similar Strings

`class Solution:    def kSimilarity(self, A: str, B: str) -> int:        def graph(x: str) -> str:            i, xarr = 0,  list(x)            while x[i] == B[i]:i += 1            # it means that xarr[i]!=B[i], we need find xarr[j]==B[i] and swap, at the same time, xarr[j] should not equal to B[j]            for j in range(i + 1, len(A)):                if xarr[j] == B[i] and xarr[j] != B[j]:                    this_xarr = xarr[:]                    this_xarr[i], this_xarr[j] = xarr[j], xarr[i]                    yield ''.join(this_xarr)                            def bfs():            Q, seen = collections.deque([(A, 0)]), {A}            while Q:                x, d = Q.popleft()                for y in graph(x):                    if y not in seen:                        if y == B:return d + 1                        seen.add(y)                        Q.append((y, d+1))        if A==B:return 0        return bfs()`

# 847. Shortest Path Visiting All Nodes

`class Solution:    def shortestPathLength(self, graph: List[List[int]]) -> int:        if any(len(g)==0 for g in graph):return 0        N = len(graph)        def bfs():            from collections import deque            Q = deque([(i, 0, {i}) for i in range(N)])            while Q:                i, d, seen = Q.popleft()                if len(seen)==N:return d                for j in graph[i]:                    this_seen = seen | {j}                    Q.append((j, d+1, this_seen))        return bfs()`
`class Solution:    def shortestPathLength(self, graph: List[List[int]]) -> int:        if any(len(g)==0 for g in graph):return 0        N = len(graph)        def bfs():            from collections import deque            Q = deque([(i, 0, {i}) for i in range(N)])            pruning = collections.defaultdict(lambda : float('inf'))            while Q:                i, d, seen = Q.popleft()                #pruning[tuple(sorted(seen))+(i,)]=d                if len(seen)==N:return d                for j in graph[i]:                    this_seen = seen | {j}                    this_key = tuple(sorted(this_seen))+(j,)                    if pruning[this_key]>d+1:                        pruning[this_key] = d+1                        Q.append((j, d+1, this_seen))        return bfs()`

# 842. Split Array into Fibonacci Sequence

`class Solution:    def splitIntoFibonacci(self, S: str) -> List[int]:        L = len(S)        def dfs(fin_res, pre_val, val, i, cur_len):            fin_res = fin_res[:]            if len(val)>L-i:return False, []            elif len(val)==L-i:                if val == S[i:] and cur_len+1>=3:                    fin_res.append(int(val))                    if len(val)==1:return True, fin_res                    elif S[i]!='0':return True, fin_res                else:return False, []            else:                if val == S[i:i+len(val)]:                    new_val = int(val)+int(pre_val)                    fin_res.append(int(val))                    return dfs(fin_res, val, str(new_val), i+len(val), cur_len+1)                else:                    return False, []        for i in range(1, len(S)-1):            if i>1 and S[0]=='0':continue            for j in range(1, len(S)-i):                if j>1 and S[i]=='0':continue                if i+j-1>=L:continue                pre_val, val = S[:i], S[i:i+j]                new_val = int(pre_val)+int(val)                #print(i,j, pre_val, val, new_val)                fin_res = [int(pre_val), int(val)]                good, res = dfs(fin_res, val, str(new_val), i+j, 2)                if good:                    if max(res)<=2**31-1:return res        return []`

# 834. Sum of Distances in Tree

`class Solution:    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:        tree = collections.defaultdict(set)        for a,b in edges:            tree[a].add(b)            tree[b].add(a)        root_nodes = [0]*N        def dfs_root_nodes(node, d,seen):            root_nodes[node] = d            seen.add(node)            for nxt_node in tree[node]:                if nxt_node not in seen:                    dfs_root_nodes(nxt_node, d+1, seen.copy())        dfs_root_nodes(0, 0, set())        res = [0]*N        def node_counter(nxt_node, seen):            #print(seen)            if len(tree[nxt_node])==1:return 1            seen.add(nxt_node)            return 1+sum(node_counter(node, seen.copy()) for node in tree[nxt_node] if node not in seen)        def dfs_node_rest_nodes(node, d, seen):            #print(node)            res[node] = d            seen.add(node)            for nxt_node in tree[node]:                if nxt_node not in seen:                    counter = node_counter(nxt_node, {node})                    this_d = d - counter + (N-counter)                    dfs_node_rest_nodes(nxt_node, this_d, seen.copy())        dfs_node_rest_nodes(0, sum(root_nodes), set())        return res`
`class Solution:    def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:        tree = collections.defaultdict(set)        res = [0] * N        count = [1] * N        for i, j in edges:            tree[i].add(j)            tree[j].add(i)def dfs(root, pre):            for i in tree[root]:                if i != pre:                    dfs(i, root)                    count[root] += count[i]                    res[root] += res[i] + count[i]def dfs2(root, pre):            for i in tree[root]:                if i != pre:                    res[i] = res[root] - count[i] + N - count[i]                    dfs2(i, root)        dfs(0, -1)        dfs2(0, -1)        return res`

# 827. Making A Large Island

`class Solution:    def largestIsland(self, grid: List[List[int]]) -> int:        R, C = len(grid), len(grid[0])        self.uf = {}        def find(x):            self.uf.setdefault(x,x)            if x!=self.uf[x]:                self.uf[x]=find(self.uf[x])            return self.uf[x]        def union(x ,y):            self.uf[find(y)] = find(x)        ones = set()        for i in range(R):            for j in range(C):                if grid[i][j]:                    x= C*i+j                    ones.add(x)                    neighbors = [(i+di,j+dj) for di, dj in [(1,0),(-1,0),(0,1),(0,-1)]]                    for r, c in neighbors:                        if 0<=r<R and 0<=c<C and grid[r][c]:                            y = C*r+c                            ones.add(y)                            union(x,y)                cnt = collections.defaultdict(int)        for i in ones:            cnt[find(i)]+=1        if not cnt:return 1        M = max(cnt.values())        if M==0:return 1        for i in range(R):            for j in range(C):                if not grid[i][j]:                    neighbors = [(i+di,j+dj) for di, dj in [(1,0),(-1,0),(0,1),(0,-1)]]                    good_nei = [(r,c) for r,c in neighbors if 0<=r<R and 0<=c<C and grid[r][c]]                    if good_nei:                        roots = set()                        for r, c in good_nei:                            y = C*r+c                            roots.add(find(y))                        new_M = 1+sum(cnt[key] for key in roots)                        M =max(M, new_M)        return M`

# 815. Bus Routes

`class Solution:    def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:        stop_bus = collections.defaultdict(set)        begin_bus = []        for i, route in enumerate(routes):            for stop in route:                if stop==S:                    begin_bus.append(i)                stop_bus[stop].add(i)        if S ==T:return 0                def bfs(b):            if T in routes[b]:return 1            from collections import deque            Q = deque([(S,b, 1)])            seen_bus = {0}            while Q:                stop, bus, d = Q.popleft()                   for stop in routes[bus]:                    for nxt_bus in stop_bus[stop]:                        if nxt_bus not in seen_bus:                            if T in routes[nxt_bus]:return d+1                            seen_bus.add(nxt_bus)                            Q.append((stop, nxt_bus, d+1))            return -1                res = [bfs(b) for b in begin_bus]        fin_res = [r for r in res if r!=-1]        return min(fin_res) if fin_res else -1`
`class Solution:    def isBipartite(self, graph: List[List[int]]) -> bool:        color = {}        def dfs(pos):            for i in graph[pos]:                if i in color:                    if color[i] == color[pos]:                        return False                else:                    color[i] = 1 - color[pos]                    if not dfs(i):                        return False            return True        for i in range(len(graph)):            if i not in color:                color[i] = 0                if not dfs(i):                    return False        return True`

--

--

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.