General

211 Word Search

Design a data structure that supports the following two operations:

void addWord(word) bool search(word) search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

class Node:
    def __init__(self):
        self.children = collections.defaultdict(Node)
        self.isWord = False
    
class WordDictionary:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = Node()
        
    
    def addWord(self, word: str) -> None:
        """
        Adds a word into the data structure.
        """
        p = self.root
        for ch in word:
            p = p.children[ch]
            
        p.isWord = True
        
    
    def search(self, word: str) -> bool:
        """
        Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
        """
        p = self.root
        
        for i, ch in enumerate(word):
            if ch == '.':
                for j in range(26):
                    ch_new = chr(ord('a') + j)
                    if p.children[ch] and self.search(word[:i] + ch_new + word[i+1:]):
                        return True
                return False
            else:
                if not p.children[ch]:
                    return False
                p = p.children[ch]
                
        return p.isWord

212 Word Search II

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.

• Use Trie to store words

• DFS search

• A boolean table to record the route

• Time: num is number of words, k is avg len of a word.

  Building trie is O(num*k), searching is O(n*m*4^k)

from collections import defaultdict
class Node:
    def __init__(self):
        self.children = defaultdict(Node)
        self.word = None
        
        
class wordDict():
    def __init__(self):
        self.root = Node()
    
     
    def insert(self, word):
        p = self.root
        for ch in word:
            p = p.children[ch]
        p.word = word
        

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        self.ans= []
        self.board = board
        w = wordDict()
        
        for word in words:
            w.insert(word)
            
        self.m, self.n = len(board), len(board[0])
        
        for i in range(self.m):
            for j in range(self.n):
                self.backtrack(i, j, w.root)
                
        return sorted(self.ans)
    
    
    def backtrack(self, i, j, node):
        c = self.board[i][j]
        
        if c not in node.children: return 
        
        if node.children[c].word and node.children[c].word not in self.ans:
            self.ans.append(node.children[c].word)
        
        self.board[i][j] = '#'
        for dy, dx in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            y, x = i+dy, j+dx
            if not (0 <= y < self.m and 0 <= x <self.n) or self.board[y][x] == '#': continue
            self.backtrack(y, x, node.children[c])
            
        self.board[i][j] = c