3 min read
Description： Given a matrix of lower alphabets and a dictionary. Find all words in the dictionary that can be found in the matrix. A word can start from any position in the matrix and go left/right/up/down to the adjacent position. One character only be used once in one word.
Example Given matrix: doaf agai dcan and dictionary:
{“dog”, “dad”, “dgdg”, “can”, “again”}
return {“dog”, “dad”, “can”, “again”}
Using trie to implement your algorithm.
class Solution:
"""
@param board: A list of lists of character
@param words: A list of string
@return: A list of string
"""
def wordSearchII(self, board, words):
# write your code here
# null
trie={}
for w in words:
t=trie
for c in w:
if c not in t:
t[c]={}
t=t[c]
#print trie
t['#']='#'
self.res=set()
self.used=[[False]*len(board[0]) for _ in range(len(board))]
for i in range(len(board)):
for j in range(len(board[0])):
self.find(board,i,j,trie,'')
return list(self.res)
def find(self,board,i,j,trie,pre):
if '#' in trie:
self.res.add(pre)
if i<0 or i>=len(board) or j<0 or j>=len(board[0]):
return
if not self.used[i][j] and board[i][j] in trie:
self.used[i][j]=True
directions = [(1,0),(-1,0),(0,1),(0,-1)]
for dr in directions:
self.find(board,i+dr[0],j+dr[1],trie[board[i][j]],pre+board[i][j])
#self.find(board,i+1,j,trie[board[i][j]],pre+board[i][j])
#self.find(board,i,j+1,trie[board[i][j]],pre+board[i][j])
#self.find(board,i-1,j,trie[board[i][j]],pre+board[i][j])
#self.find(board,i,j-1,trie[board[i][j]],pre+board[i][j])
self.used[i][j]=Falsethree key parts:
Description Given a 2D grid, each cell is either a wall 2, an house 1 or empty 0 (the number zero, one, two), find a place to build a post office so that the sum of the distance from the post office to all the houses is smallest. Return the smallest sum of distance. Return -1 if it is not possible. You cannot pass through wall and house, but can pass through empty. You only build post office on an empty.
Example Given a grid: 0 1 0 0 0 1 0 0 2 1 0 1 0 0 0 return 8, You can build at (1,1). (Placing a post office at (1,1), the distance that post office to all the house sum is smallest.)
class Solution:
"""
@param grid: a 2D grid
@return: An integer
"""
def shortestDistance(self, grid):
# write your code here
if not grid and not grid[0]:
return -1
m = len(grid)
n = len(grid[0])
dist = [[sys.maxint for _ in range(n)] for _ in range(m)]
reachable_count = [[0 for _ in range(n)] for _ in range(m)]
min_dist = sys.maxint
buildings = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
self.bfs(grid, i, j, dist, m, n, reachable_count)
buildings += 1
for i in range(m):
for j in range(n):
if reachable_count[i][j] == buildings and dist[i][j] < min_dist:
min_dist = dist[i][j]
return min_dist if min_dist != sys.maxint else -1
def bfs(self, grid, i, j, dist, m, n, reachable_count):
visited = [[False for _ in range(n)] for _ in range(m)]
visited[i][j] = True
q = collections.deque([(i,j, 0)])
while q:
i, j, l = q.popleft()
if dist[i][j] == sys.maxint:
dist[i][j] = 0
dist[i][j] += l
for x, y in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nx, ny = i+x, j+y
if nx > -1 and nx < m and ny > -1 and ny < n and not visited[nx][ny]:
visited[nx][ny] = True
if grid[nx][ny] == 0:
q.append((nx, ny, l+1))
reachable_count[nx][ny] += 1