Given a 2D board and a list of words from the dictionary, find all words in the board.
很像找詞遊戲，看看版面上有沒有要搜尋的詞。不過跟一般的規則不同的是，它可以轉彎。
此題列在 trie 章節內，所以自然而然將目標字詞寫入 trie 內，再用 y x 遍歷整個版面，把board[y][x]放入搜尋就可以了。
重複出現的字詞只算一個，所以找到的字詞放入 set 或是 dict當key，最後再取出來。
這題我是很快就解出來的，關鍵之處不是如何把詞放入 trie，而是搜尋要如何進行。
如果學過回溯法，應該很快就知道找路徑的寫法是該怎麼進行。
當遍歷整個版面，取得 y x，如果 board[y][x] 在 trie 內，就繼續往四週找，看四週的字是否有出現下一層。
因為限制不能回頭，所以用一個 memo 去紀錄步驟(座標)，接下來就避免重複尋找已經走過的路徑。(if (y,x) in memo)
回溯法的關鍵寫法：是在往下遞迴之前才加入步驟，在遞迴結束後要刪除之前加入的步驟。這就像是回到上一步，再往下一個方向嘗試。
最終會將全部可走的都走過，再一一收回步驟，因此當搜尋完畢之後 memo 會是空的。
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
if board and board[0]:
rows, cols = len(board), len(board[0])
# create trie
trie = {}
for word in words:
cur = trie
for char in word:
if char not in cur:
cur[char] = {}
cur = cur[char]
cur['end'] = word
#
memo = {*""}
findWords = {*""}
def search(y, x, level):
if board[y][x] in level:
level = level[board[y][x]]
if 'end' in level:
findWords.add(level['end'])
if y-1 >= 0 and (y-1,x) not in memo:
memo.add((y,x))
search(y-1, x, level)
memo.discard((y,x))
if x-1 >= 0 and (y,x-1) not in memo:
memo.add((y,x))
search(y, x-1, level)
memo.discard((y,x))
if y+1 < rows and (y+1,x) not in memo:
memo.add((y,x))
search(y+1, x, level)
memo.discard((y,x))
if x+1 < cols and (y,x+1) not in memo:
memo.add((y,x))
search(y, x+1, level)
memo.discard((y,x))
for y in range(rows):
for x in range(cols):
memo.clear()
search(y, x, trie)
return list(findWords)
