题解 | #童谣寻找问题# java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param board char字符型二维数组
     * @param word string字符串
     * @return bool布尔型
     */
    public boolean exist (char[][] board, String word) {
        // write code here
        if (board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        int m = board.length;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (backtrack(board, word, i, j, 0, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean backtrack(char[][] board, String word, int i, int j,
                              int index,
                              boolean[][] visited) {
        if (index == word.length()) {
            return true;
        }
        int m = board.length;
        int n = board[0].length;
        if (i < 0 || i >= m || j < 0 || j >= n ||
                visited[i][j] || board[i][j] != word.charAt(index)) {
            return false;
        }
        visited[i][j] = true;
        if (backtrack(board, word, i - 1, j, index + 1, visited)
                || backtrack(board, word, i + 1, j, index + 1, visited)
                || backtrack(board, word, i, j - 1, index + 1, visited)
                || backtrack(board, word, i, j + 1, index + 1, visited)) {
            return true;
        }
        visited[i][j] = false;
        return false;
    }
}

编程语言是 Java。

该题考察的知识点包括多维数组遍历、回溯算法

解释如下：

• exist 方法：在二维字符数组中搜索是否存在可以组成给定字符串的路径。首先进行数组的遍历，对每个单元格调用 backtrack 方法进行回溯搜索。
• backtrack 方法：采用回溯算法，递归地尝试从当前单元格开始，向上、下、左、右四个方向移动，尝试组成给定字符串。如果能成功组成字符串，返回 true，否则回溯。在进行搜索过程中，通过记录已访问的单元格来避免重复访问。