79. Word Search - Medium

前往題目

之前寫的文章

想法

• 找到首字母
• DFS可能的路徑

思路

1. 使用Backtracking(DFS)
2. 每個cell都要DFS，沒有更優的演算法了
3. 走過的path就標記，然後往上下左右去確認是否字母匹配
4. 匹配就前往其他格子，並且匹配下一個字母，直到全部都符合

Code

class Solution {
    int ROWS;
    int COLS;

    public boolean exist(char[][] board, String word) {
        ROWS = board.length;
        COLS = board[0].length;
        // 拜訪每一格
        for (int row = 0; row < ROWS; ++row) {
            for (int col = 0; col < COLS; ++col) {
                // 在每一格嘗試DFS
                if (backtrack(row, col, 0, board, word)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean backtrack(int r, int c, int i, char[][] board, String word) {
        // 匹配成功
        if (i >= word.length()) return true;
        
        // Check boundary and character
        if (r < 0 || r >= ROWS || c < 0 || c >= COLS || word.charAt(i) != board[r][c]) return false;

        boolean exist = false;

        if (board[r][c] == word.charAt(i)) {
            // Mark as visited
            board[r][c] += 100;

            // Check all the directions
            exist = backtrack(r + 1, c, i + 1, board, word) ||
                    backtrack(r - 1, c, i + 1, board, word) ||
                    backtrack(r, c + 1, i + 1, board, word) ||
                    backtrack(r, c - 1, i + 1, board, word);
            // Mark as unvisited
            board[r][c] -= 100;
        }

        return exist;
    }
}