Word Search 2

This question is a little bit dumb hard, but it's a standard Google style question and expose quite a lot problems in my code. Thanks to it! Plus, plus, plus....

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:

Input: 
words = ["oath","pea","eat","rain"] and board =
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Output: ["eat","oath"]

Note:
You may assume that all inputs are consist of lowercase letters a-z.

Solution without Optimization. 
Using DFS的暴力解法

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70

class Solution: """ @param board: A list of lists of character @param words: A list of string @return: A list of string """ # DFS 的暴力解法 def wordSearchII(self, board, words): # write your code here deltaMove = [(-1, 0), (1, 0), (0, -1), (0, 1)] self.res = [] if (len(board) == 0): return self.res w, h = len(board[0]), len(board) # 以后初始化都用这个！list comprehension visited = [[False for i in xrange(w)] for j in xrange(h)] for i in range(h): for j in range(w): word = board[i][j] visited[i][j] = True self.searchHelperDFS(board, visited, words, word, deltaMove, (i, j)) visited[i][j] = False return self.res def searchHelperDFS(self, board, visited, words, word, deltaMove, pos): # 如果word已经被加过了，跳过 if word in words and word not in self.res: self.res.append(word[:]) # 不return, 当找到了word之后需要继续找。有可能已经找到的word是剩下的word的前缀 # return for i in xrange(0, len(deltaMove)): # 用lambda实现tuple 成员的加减。。 nextpos = tuple(map(lambda x, y: x + y, deltaMove[i], pos)) if (not self.isValidMove(visited, nextpos)): continue nr, nc = nextpos[0], nextpos[1] word += board[nr][nc] visited[nr][nc] = True self.searchHelperDFS(board, visited, words, word, deltaMove, nextpos) visited[nr][nc] = False word = word[:-1] def searchHelperBFS(self, ): def isValidMove(self, visited, pos): if (pos[0] < 0 or pos[1] < 0 or pos[0] >= len(visited) or pos[1] >= len(visited[0]) or visited[pos[0]][pos[1]]): return False return True sol = Solution() board = ["doaf","agai","dcan"] words = ["dog","dad","dgdg","can","again"] res = sol.wordSearchII(board, words) print res

Optimization: Using Trie.