🌕 79. 单词搜索

难度: 🌕

问题描述

---

解法

class Solution {
    public boolean exist(char[][] board, String word) {
        // 思路：
        // 回溯
        int row = board.length;
        int col = board[0].length;
        int len = word.length();
        for(int i = 0; i < row; i ++) {
            for(int j = 0; j < col; j ++) {
                if(board[i][j] == word.charAt(0)) {
                    if(mySol(board, word, row, col, len, 0, i, j)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean mySol(char[][] board, String word, int row, int col, int len, int index, int i, int j) {
        // 递归终止条件
        if(i < 0 || i >= row || j < 0 || j >= col) {
            return false;
        }
        if(word.charAt(index) != board[i][j]) {
            return false;
        }
        if(index == len - 1) {
            return true;
        }
        // index < len - 1
        char cur = board[i][j];
        board[i][j] = '#'; // 做标记去重
        boolean res = mySol(board, word, row, col, len, index + 1, i - 1, j) 
                || mySol(board, word, row, col, len, index + 1, i + 1, j)
                || mySol(board, word, row, col, len, index + 1, i, j - 1)
                || mySol(board, word, row, col, len, index + 1, i, j + 1);
        if(res == true) {
            return res;
        } else {
            board[i][j] = cur; // 还原
            return res;
        }
    }
}

---

输出