Question: https://leetcode.com/problems/word-search-ii/
Question Name: Word Search II
In general, this is a question with DFS/BFS of graph. Additionally, we need some optimizations:
- Use prefix tree to terminate the search early;
- Remove the found word in the prefix tree;
- Use bigrams to filter out the impossible words before constructing prefix tree;
- Convert the string (a list of chars) to a list of int, which is used as index of prefix tree node.
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 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 | class TrieNode(object): def __init__(self): """ Initialize the prefix tree node. """ self.word = None self.sons = [None for _ in xrange(26)] def add_word(self, word): """ Inserts a word into the trie. :type word: str :rtype: void """ current = self for letter in word: sons_index = ord(letter) - ord("a") if current.sons[sons_index] == None: current.sons[sons_index] = TrieNode() current = current.sons[sons_index] current.word = word return def remove_word(self, word): """ Remove a word from the trie, assuming it exists. :type word: str :rtype: void """ path = [self] for letter in word: path.append(path[-1].sons[ord(letter) - ord("a")]) path[-1].word = None for index in xrange(-1, -len(path), -1): letter = word[index] node = path[index] is_leaf = all([son == None for son in node.sons]) if is_leaf and node.word == None: path[index-1].sons[ord(letter) - ord("a")] = None return class Solution(object): def findWordsHelper(self, board, node, row, column): """ :type board: List[List[str]] :type node: TriesNode :type starting_x: int :type starting_y: int :rtype: List[str] """ result = [] letter = board[row][column] if letter == "#": return result son = node.sons[letter] if son == None: return result if son.word != None: result.append(son.word) self.root.remove_word(son.word) # Prepare the candidate letters to extend current prefix. board[row][column] = "#" if row != 0: for res in self.findWordsHelper(board, son, row - 1, column): result.append(res) if row != self.row_count - 1: for res in self.findWordsHelper(board, son, row + 1, column): result.append(res) if column != 0: for res in self.findWordsHelper(board, son, row, column - 1): result.append(res) if column != self.column_count - 1: for res in self.findWordsHelper(board, son, row, column + 1): result.append(res) board[row][column] = letter return result def findWords(self, board, words): """ :type board: List[List[str]] :type words: List[str] :rtype: List[str] """ bigrams = set() row_count = len(board) column_count = len(board[0]) for row in xrange(row_count): for column in xrange(column_count): if row != row_count - 1: bigrams.add(board[row][column] + board[row + 1][column]) if column != column_count - 1: bigrams.add(board[row][column] + board[row][column + 1]) bigrams |= set([bigram[::-1] for bigram in bigrams]) root = TrieNode() for word in words: for index in xrange(len(word) - 1): if word[index : index + 2] not in bigrams: break else: root.add_word(word) result = [] if root.word != None: # Empty string result.add(root.word) root.word = None self.row_count = row_count self.column_count = column_count self.root = root board = [[ord(cell) - ord("a") for cell in row] for row in board] for row in xrange(row_count): for column in xrange(column_count): for res in self.findWordsHelper(board, root, row, column): result.append(res) return result |