212. Word Search II

Question: Word Search II

Solution

覺得太難的話，可以先參照 79. Word Search 這一題：

接著學會使用 Trie，可以參考 208. Implement Trie (Prefix Tree) 這一題

想法：

1. 找單字 → Prefix Tree → Trie

   1. 將單字做成 Trie 的字典方便查找

2. 答案不重複 res → set()

3. 拜訪過的路徑 visti (i, j)不重複 → set()

4. 找每一格旁邊的字 → DFS

   1. 終止條件

      1. 超出邊界
         • i < 0
         • j < 0
         • i > row - 1
         • j > column - 1
      2. (i, j) 是來時路：(i, j) is visited
      3. 相鄰的字母，不存在現在的 node 的 children 裡：board[i][j] not in curr_node.children

   2. 遞迴條件

      board[i][j] in curr_node.children:

      1. word += board[i][j]

      2. curr_node = curr_node.children(board[i][j])

      3. 如果現在的 node 是最後一個完整的字，就將 word 加入 res: 
         if curr_node.end_of_word == True: res.add(word)

      4. 將 (i, j) 加入 visit: visit.add((i, j))

      5. dfs 找他的鄰居

         • 上
           

           dfs(i - 1, j, curr_node, word)

         • 下
           

           dfs(i + 1, j, curr_node, word)

         • 左
           dfs(i, j - 1, curr_node, word)

         • 右
           dfs(i, j + 1, curr_node, word)

      6. DFS 完 (i, j) 所有可能路徑後，要將其移除：visit.remove((i, j))

5. for loop 每一格
   

   for i in range(row):

   for j in range(column):

   dfs(i, j, curr_node, "")

6. 將 res 轉成 list: list(res)

• TimeComplexity: O(m * n * 4 ^ (m * n))

  每一格都要找過，總共 m * n 格： m * n
  要找每個 word 時一次都找四個方向，會找 word 長度: 4 ^ word_len * 多少 word
  worse case = m * n * 4 ^ (m * n)

class TrieNode:

def __init__(self):

self.children = dict()

self.end_of_word = False

class Trie:

def __init__(self):

self.root = TrieNode()

def insert(self, word):

curr = self.root

for c in word:

if c not in curr.children:

curr.children[c] = TrieNode()

curr = curr.children[c]

curr.end_of_word = True

class Solution:

def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:

trie = Trie()

for word in words:

trie.insert(word)

res, visit = set(), set()

def dfs(i, j, curr_node, word):

if (i < 0 or

j < 0 or

i > row - 1 or

j > column - 1 or

board[i][j] not in curr_node.children or

(i, j) in visit):

return

word += board[i][j]

curr_node = curr_node.children[board[i][j]]

if curr_node.end_of_word == True:

res.add(word)

visit.add((i, j))

dfs(i + 1, j, curr_node, word)

dfs(i - 1, j, curr_node, word)

dfs(i, j + 1, curr_node, word)

dfs(i, j - 1, curr_node, word)

visit.remove((i, j))

column, row = len(board[0]), len(board)

for r in range(row):

for c in range(column):

dfs(r, c, trie.root, "")

return list(res)

Video Solution