jinhuang1102

79. Word Search

Apr 24th, 2019
213
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.16 KB | None | 0 0
  1. """
  2. 79. Word Search
  3. 这道题有一个有意思的方法,可能很大程度的提高计算速度。就是用Counter来数是否borad里面的字母能够满足word里面的祖母个数
  4. """
  5. from collections import Counter
  6.  
  7. class Solution(object):
  8.     def search(self, board, x, y, word, visited):
  9.         if len(word) == 0:
  10.             return True
  11.        
  12.         dx = [0,0,1,-1]
  13.         dy = [1,-1,0,0]
  14.        
  15.         for i in range(0, 4):
  16.             rx = x + dx[i]
  17.             ry = y + dy[i]
  18.             if rx < 0 or rx == len(board) or ry <0 or ry == len(board[0]):
  19.                 continue
  20.             else:
  21.                 if board[rx][ry] == word[0] and not (rx, ry) in visited:
  22.                     visited.add((rx,ry))
  23.                     if self.search(board, rx, ry, word[1:], visited):
  24.                         return True
  25.                     visited.remove((rx,ry))
  26.        
  27.         return False
  28.                    
  29.                    
  30.    
  31.     def exist(self, board, word):
  32.         """
  33.        :type board: List[List[str]]
  34.        :type word: str
  35.        :rtype: bool
  36.        """
  37.         if not board:
  38.             return False
  39.        
  40.         # Counter1 统计board中每个字母的个数
  41.         cnt = Counter()
  42.         for i in range(0, len(board)):
  43.             for j in range(0, len(board[0])):
  44.                 cnt[board[i][j]] += 1
  45.        
  46.        
  47.        
  48.         # Counter2 统计word中每个字母的个数    
  49.         w_cnt = Counter()
  50.         for i in range(0, len(word)):
  51.             w_cnt[word[i]] += 1
  52.          
  53.        
  54.    
  55.         # 如果word中的字母的个数大于 board中字母的个数 return False
  56.         for l, l_cnt in w_cnt.items():
  57.             if not l in cnt or l_cnt > cnt[l]:
  58.                 return False
  59.        
  60.         visited = set()
  61.         for i in range(0, len(board)):
  62.             for j in range(0, len(board[0])):
  63.                 if board[i][j] == word[0]:
  64.                     visited.add((i,j))
  65.                     if self.search(board, i, j, word[1:], visited):
  66.                         return True
  67.                     visited.remove((i,j))
  68.         return False
Advertisement
Add Comment
Please, Sign In to add comment