Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """
- 79. Word Search
- 这道题有一个有意思的方法,可能很大程度的提高计算速度。就是用Counter来数是否borad里面的字母能够满足word里面的祖母个数
- """
- from collections import Counter
- class Solution(object):
- def search(self, board, x, y, word, visited):
- if len(word) == 0:
- return True
- dx = [0,0,1,-1]
- dy = [1,-1,0,0]
- for i in range(0, 4):
- rx = x + dx[i]
- ry = y + dy[i]
- if rx < 0 or rx == len(board) or ry <0 or ry == len(board[0]):
- continue
- else:
- if board[rx][ry] == word[0] and not (rx, ry) in visited:
- visited.add((rx,ry))
- if self.search(board, rx, ry, word[1:], visited):
- return True
- visited.remove((rx,ry))
- return False
- def exist(self, board, word):
- """
- :type board: List[List[str]]
- :type word: str
- :rtype: bool
- """
- if not board:
- return False
- # Counter1 统计board中每个字母的个数
- cnt = Counter()
- for i in range(0, len(board)):
- for j in range(0, len(board[0])):
- cnt[board[i][j]] += 1
- # Counter2 统计word中每个字母的个数
- w_cnt = Counter()
- for i in range(0, len(word)):
- w_cnt[word[i]] += 1
- # 如果word中的字母的个数大于 board中字母的个数 return False
- for l, l_cnt in w_cnt.items():
- if not l in cnt or l_cnt > cnt[l]:
- return False
- visited = set()
- for i in range(0, len(board)):
- for j in range(0, len(board[0])):
- if board[i][j] == word[0]:
- visited.add((i,j))
- if self.search(board, i, j, word[1:], visited):
- return True
- visited.remove((i,j))
- return False
Advertisement
Add Comment
Please, Sign In to add comment