# Hard Graph

1. build graph
2. prune infeasible branches in an early stage by comparing the steps to move to a specified node. Do not add them if move steps of new node are larger than before.
3. Then follow standard BFS approach and recording the number of new generated nodes for the new graph from both i to j and j to i. Then the final results of reachable new added nodes will be min(n, i to j + j to i) as they may have overlaps.
`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            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)        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':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 = *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 = *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 =  * N        count =  * 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)        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.

## Recommended from Medium ## Reimagining the customer onboarding experience with Box, Salesforce, DocParser, Twilio, and… ## Interview with Arnold Bansemer, Particl Desktop’s Lead Developer ## Like on #Instagram #foto: http://ift.tt/2jIC4TP | @Regrann from… ## OAK Network — Dapp Contest and Grant Program Launch ## Vultr vs Linode vs Digitalocean: disk performance ## Homebaked | Raspberry Pi + Django Home Server ## The Simplest Math Problem We Still Can’t Solve — Part 1  ## Jimmy Shen

Data Scientist/MLE/SWE @takemobi

## Fraud Prevention: Exploration-Exploitation Tradeoff in AI-based Systems ## AI-powered Expert Network… What does this mean? ## A look into Hierarchical clustering ## What is Accuracy, Precision, Recall & F1 Score? 