java - Java 中 char 数组中字符串的所有可能组合

Question

我正在做一个关于 Java 的学校项目，我也被分配了。现在我对项目的一部分遇到了问题，我无法弄清楚。应用程序必须从二维字符数组(char[][] board)生成所有可能的单词组合(可以通过字典验证)。该板是动态的，因为用户可以选择比例:4x4、5x5、4x5、5x4、4x6，...所以我想嵌套循环在这里不合适，如果我错了，请纠正我。单词必须水平、垂直和对角生成。 4x4 板的示例:

|你|一个 |你| s |

| n | n |我|我|

|一个 |哦|电子| b |

|电子|你|电子| z |

    Code was completely wrong.

另一个想法可能是暴力破解板上所有可能的路径，然后尝试这些保存的路径来验证它是否是一个单词。

提前致谢!

Answer 1

解决这个问题的一种方法是:

for each path on the board
    if corresponding word in dictionary
        print it

要查找所有路径，您可以调整任何 graph traversal algorithm .

现在这会非常慢，因为这种尺寸的板有很多路径(对于具有 n 个单元的板，我们最多可以有n * 4 ^ (n - 1) 路径，因此对于 5 x 5 的板，您将拥有类似 25 * 2 ^ 50 ~= 10^16 的路径。

对此进行改进的一种方法是交错遍历图形并检查字典，如果当前路径的单词不是字典单词的前缀，则中止:

class Board {

    char[][] ch;
    boolean[][] visited;

    Trie dictionary;

    void find() {
        StringBuilder prefix = new StringBuilder();
        for (int x = 0; x < maxx; x++) {
            for (int y = 0; y < maxy; y++) {
                walk(x, y, prefix);
            }
        }
     }

    void walk(int x, int y, StringBuilder prefix) {
        if (!visited[x][y]) {
            visited[x][y] = true;
            prefix.append(ch[x][y]);

            if (dictionary.hasPrefix(prefix)) {
                if (dictionary.contains(prefix)) {
                    System.out.println(prefix);
                }

                int firstX = Math.max(0, x - 1);
                int lastX = Math.min(maxx, x + 1);
                int firstY = Math.max(0, y - 1);
                int lastY = Math.min(maxy, y + 1);
                for (int ax = firstX; ax <= lastX; ax++) {
                    for (int ay = firstY; ay <= lastY; ay++) {
                        walk(ax, ay, prefix);
                    }
                }
            }

            prefix.setLength(prefix.length() - 1);
            visited[x][y] = false;
        }
    }

如您所见，方法 walk 调用自身。该技术被称为recursion .

剩下的问题就是为字典找到支持高效前缀查询的数据结构。最好的此类数据结构是 Trie 。遗憾的是，JDK 不包含实现，但幸运的是，编写一个实现并不难。

注意:此答案中的代码尚未经过测试。