Leetcode面试经典150题-79.搜索单词

题目比较简单，回溯最基础的题，记得除非覆盖，否则一定要恢复现场就行

解法都在代码里，不懂就留言或者私信

class Solution {
    public boolean exist(char[][] board, String word) {
        int m = board.length; 
        int n = board[0].length;
        if(m * n < word.length()) {
            return false;
        }
        /**转换成字符数组 */
        char[] wordArr = word.toCharArray();
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[i].length; j++) {
                /**任何一个成功，直接返回,这里加一下等于判断提高效率*/
                if(process(board, wordArr, i , j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean process(char[][] board, char[] wordArr, int row, int col, int curIndex) {
        if(curIndex == wordArr.length) {
            return true;
        }
        if(row < 0 || row >= board.length || col < 0 || col >= board[row].length || board[row][col] != wordArr[curIndex]) {
            return false;
        }
        /**用过的标记成0(数字0)并在此之前记录原始值，用于失败后的恢复现场*/
        char orginChar = board[row][col];
        board[row][col] = '0';
        /**上下左右都试一下 */
        boolean up = process(board, wordArr, row - 1, col, curIndex + 1);
        boolean right = process(board, wordArr, row, col + 1, curIndex + 1);
        boolean down = process(board, wordArr, row + 1, col, curIndex + 1);
        boolean left = process(board, wordArr, row, col - 1, curIndex + 1);
        /**任何一个成功就是成功，不再继续尝试 */
        if(up || right || down || left) {
            return true;
        }
        /**如果失败了下个需要重新从这个位置开始尝试，这里要恢复现场 */
        board[row][col] = orginChar;
        /**失败了返回false */
        return false;
    }
}