# 79. Word Search
#### Difficulty: Medium
link: https://leetcode.com/problems/word-search/

### 1. Backtracking
#### $O(m*n*4^k)$ runtime, $O(k)$ space
###### k = len(word)

題目說從mxn的grid找到word這個字，並且同一格不能走兩次，我們用backtracking來檢查所有可能的組合，看看是否有word存在。

dfs函數來實作backtracking，x和y代表現在要檢查的座標，index代表檢查到word的第index個char。函數直接返回Boolean可以讓程式碼更簡潔。

避免重複走到之前走過的格子，有個小技巧能不用額外空間來記這件事，直接將board走過的地方改成"#"，因為board只會出現英文字，所以就一定不會match word。

由於grid上的每一格都可能是起點，所以每個字都檢查。

優化有兩個，第一個是檢查board是否有足夠word的char數，第二個是從字頻較少的word那端開始找起。

##### python

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        board_cnt = Counter([ch for row in board for ch in row])
        word_cnt = Counter(word)
        
        # optimization 1
        for ch in word_cnt:
            if word_cnt[ch] > board_cnt[ch]:
                return False
        
        # optimization 2
        word = word if word_cnt[word[0]] < word_cnt[word[-1]] else word[::-1]
        
        m, n = len(board), len(board[0])
        
        def dfs(x, y, index):
            if board[x][y] != word[index]:
                return False
            
            if index == len(word) - 1:
                return True
            
            board[x][y] = "#"
            for nx, ny in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:
                if 0 <= nx < m and 0 <= ny < n and dfs(nx, ny, index+1):
                    return True
            board[x][y] = word[index]
            
            return False
        
        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        
        return False

###### tags: `leetcode`