如何计算字符矩阵中一个单词的所有出现次数？

Question

如何计算字符矩阵中一个单词的所有出现次数？

javaalgorithmmatrixdepth-first-searchword-count

3

问题

给定一个 m x n 的二维字符矩阵和一个单词，找出该单词在矩阵中出现的次数。

该单词可以由相邻的水平或垂直单元格中的字母构建而成，相邻的单元格必须按照单词中字母的顺序排列。

注意：同一个字母的单元格不能重复使用。

输入格式

第一行包含两个用空格分隔的整数 m 和 n，表示矩阵的行数和列数。接下来 m 行，每行包含 n 个字符。最后一行包含要查找的单词。

约束条件

1 <= m, n <= 5

1 <= lengthOf(word) <= 30

enter code here

输出格式

在二维棋盘中打印给定单词的总数。

示例输入

3 4
HDST
ANEO
BENY
NEST  // word

样例输出

同时我不能满足测试用例。

5 5
LACOO 
OOOCL
NLOOO
ECOCO
MECOO
COOLOOC

输出应该是

我的代码

 public static void main(String[] args) {
        int m, n;
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();

        char[][] board = new char[m][n + 1];
        for (int i = 0; i < m; i++) {
            String temp = sc.next();
            board[i] = temp.toCharArray();
        }

        String word = sc.next();

        System.out.print(new Result().countWord(board, word, m, n));
    }

static class Result {
        static boolean[][] visited;
        static int count = 0;

        int countWord(char board[][], String word, int m, int n) {
            visited = new boolean[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == word.charAt(0)) {
                        if(searchWord(board, word, i, j, m, n, 0))
                            count++;
                    }
                }
            }
            return count;
        }

        static boolean searchWord(char board[][], String word, int i, int j, int m, int n, int index) {
            if (index == word.length()) {
                count++;
                return true;
            }

            if (i < 0 || j < 0 || i >= m || j >= n)
                return false;

            if (visited[i][j] || board[i][j] != word.charAt(index))
                return false;

            visited[i][j] = true;

            if (searchWord(board, word, i - 1, j, m, n, index + 1) ||
                    searchWord(board, word, i + 1, j, m, n, index + 1) ||
                    searchWord(board, word, i, j - 1, m, n, index + 1) ||
                    searchWord(board, word, i, j + 1, m, n, index + 1)) {
                return true;
            }

            visited[i][j] = false;
            return false;
        }
    }

- Anonymous

你能分享一下主函数吗？这样有助于我们进行测试。 - Mr. Brickowski

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- JANO · Accepted Answer

我认为你的问题在于，如果找到了你要查找的单词，你会返回所有的调用。然而，即使你找到了一个单词，你仍然希望搜索所有其他可能性，因为你要查找的单词可以从同一单元格开始多次出现。

因此，我建议将dfs函数中的布尔返回值删除，因为即使找到了单词，你仍然希望搜索其他可能性。我使用你提供的示例输入测试了以下代码，看起来它是有效的。

static void searchWord(char board[][], String word, int i, int j, int m, int n, int index) {

    if (i < 0 || j < 0 || i >= m || j >= n)
        return;

    if (visited[i][j] || board[i][j] != word.charAt(index))
        return;

    if (index + 1 == word.length()) {
        count++;
        return;
    }

    visited[i][j] = true;

    searchWord(board, word, i - 1, j, m, n, index + 1);
    searchWord(board, word, i + 1, j, m, n, index + 1);
    searchWord(board, word, i, j - 1, m, n, index + 1);
    searchWord(board, word, i, j + 1, m, n, index + 1);

    visited[i][j] = false;
}

编辑：我还必须更改您的if语句的顺序，否则您将四次计算每个出现次数。