:type board: List[List[str]] :type words: List[str] :rtype: List[str]
(self, board, words)
| 69 | """ |
| 70 | class Solution(object): |
| 71 | def findWords(self, board, words): |
| 72 | """ |
| 73 | :type board: List[List[str]] |
| 74 | :type words: List[str] |
| 75 | :rtype: List[str] |
| 76 | """ |
| 77 | |
| 78 | result = [] |
| 79 | words = set(words) |
| 80 | |
| 81 | trie = {} |
| 82 | for i in words: |
| 83 | t = trie |
| 84 | for x in i: |
| 85 | if x not in t: |
| 86 | t[x] = {} |
| 87 | t = t[x] |
| 88 | t['!'] = '!' |
| 89 | |
| 90 | def find(board, x, y, word, pre): |
| 91 | # print(word) |
| 92 | if '!' in word: |
| 93 | result.append(pre) |
| 94 | |
| 95 | for w in word: |
| 96 | raw = board[y][x] |
| 97 | board[y][x] = 0 |
| 98 | |
| 99 | # up |
| 100 | if y-1 >= 0 and board[y-1][x] == w: |
| 101 | find(board, x, y-1, word[w], pre+w) |
| 102 | # down |
| 103 | if y+1 < len(board) and board[y+1][x] == w: |
| 104 | find(board, x, y+1, word[w], pre+w) |
| 105 | |
| 106 | # left |
| 107 | if x-1 >= 0 and board[y][x-1] == w: |
| 108 | find(board, x-1, y, word[w], pre+w) |
| 109 | |
| 110 | # right |
| 111 | if x+1 < len(board[0]) and board[y][x+1] == w: |
| 112 | find(board, x+1, y, word[w], pre+w) |
| 113 | |
| 114 | board[y][x] = raw |
| 115 | |
| 116 | maps = {} |
| 117 | |
| 118 | for i in range(len(board)): |
| 119 | for j in range(len(board[0])): |
| 120 | try: |
| 121 | maps[board[i][j]].append((i,j)) |
| 122 | except: |
| 123 | maps[board[i][j]] = [(i,j)] |
| 124 | |
| 125 | for i in trie: |
| 126 | if maps.get(i): |
| 127 | xy = maps.get(i) |
| 128 | for j in xy: |