单词搜索

Problem: 79.单词搜索

基本思路

典型的棋盘探索问题，使用回溯（DFS）算法解决。可以使用位运算标记使用的过的棋盘位置。


....
/** 标记 */
board[i][j] |= 0x100;
....
/** 去标记 */
board[i][j] ^= 0x100;

代码

Java


class Solution {
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    boolean dfs(char[][] board, String word, int i, int j, int length) {
        if (board[i][j] != word.charAt(length)) {
            return false;
        } else if (word.length() == length + 1) {
            return true;
        }
        board[i][j] |= 0x100;
        if ((i > 0 && (board[i - 1][j] & 0x100) == 0 && dfs(board, word, i - 1, j, length + 1))
            || (j > 0 && (board[i][j - 1] & 0x100) == 0 && dfs(board, word, i, j - 1, length + 1))
            || (i < board.length - 1 && (board[i + 1][j] & 0x100) == 0 && dfs(board, word, i + 1, j, length + 1))
            || (j < board[0].length - 1 && (board[i][j + 1] & 0x100) == 0 && dfs(board, word, i, j + 1, length + 1))) {
            return true;
        }
        board[i][j] ^= 0x100;
        return false;
    }
}

复杂度分析

时间复杂度：。为网格的长度与宽度，为字符串 word 的长度。网格的每个位置探索次，总计次；每次探索除了在 word 的第一个字符位置需要进行次探索，其余位置仅探索次。

空间复杂度：。栈的深度最大为字符串 word 的长度。