Hard Graph

from collections import deque
class 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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store