【Check 62】2024-04-26 - 79. 单词搜索

[larscheng]

79. 单词搜索

[larscheng]

思路

• 从矩阵的左上角为起点，开始递归向相邻元素搜索有无与单词第k个字符相等的元素
• 例如，起点元素==word[k]，则递归找起点相邻位置有无字符==word[k+1]
• 直到匹配完word所有字符
• 递归匹配过程中如果相邻四周元素没有与word字符相同的，则剪支操作，并且进行回溯重置

  代码

class Solution { public boolean exist(char[][] board, String word) { int m = board.length; int n = board[0].length; boolean[][] used = new boolean[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (check(board, used, i, j, word, 0)) { return true; } } } return false; }

private boolean check(char[][] board, boolean[][] used, int i, int j, String word, int k) {
    if (board[i][j] != word.charAt(k)) {
        return false;
    } else if (k == word.length() - 1) {
        return true;
    }
    boolean result = false;
    used[i][j] = true;
    int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    for (int[] direction : directions) {
        //递归逐个找相邻元素，一直找到不想等的，或者找到最后一个字符结束
        int newI = direction[0] + i;
        int newJ = direction[1] + j;
        if (newI >= 0 && newI < board.length && newJ >= 0 && newJ < board[0].length) {
            if (!used[newI][newJ] && check(board, used, newI, newJ, word, k + 1)) {
                result = true;
                break;
            }
        }
    }
    used[i][j] = false;
    return result;
}

}