$ cat ./coding/212-word-search-ii.md

────────────────────────────────────────────────────────────

212. Word Search II

這一題是 79. Word Search 的進階版，原先我們要找的是給定一個字串，看這個一個字串是否存在，這題是給定很多字串，要看哪些字串存在？

第一個直覺的想法是，那就把第一題的解法把字串一個一個檢查就好，但是這樣的方法很明顯會超時。

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        rows = len(board)
        cols = len(board[0])
        directions = [(1,0),(-1,0),(0,1),(0,-1)]
        def backtrack(r, c, word):
            if len(word) == 0:
                return True
            if 0 <= r < rows and 0 <= c < cols and board[r][c] == word[0]:
                board[r][c] = '#'
                for dr, dc in directions:
                    if backtrack(r+dr, c+dc, word[1:]):
                        board[r][c] = word[0]
                        return True
                board[r][c] = word[0]
            return False
        ans = set()

        for word in set(words):
            for r in range(rows):
                for c in range(cols):
                    if backtrack(r, c, word):
                        ans.add(word)
        return ans

$ ls ./coding/ | grep -v 212-word-search-ii