来自Java中char数组的字符串的所有可能组合

问题描述：

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

| u | a | u | s |

| n | n |我|我|

| a | o | e | b |

| e | u | e | z |

Code was completely wrong.

另一个想法可能是蛮力在黑板上每一个可能的路径，然后尝试那些保存路径，以验证它是否是一个词或没有。

在此先感谢！

你是什么意思与“在板上产生的话”？你的输入是什么，它的输出是什么？ – meriton

该应用程序在随机基础上（随机字符）生成板，然后必须在多个方向上（水平，垂直和对角线）找到板上所有可能的单词，并且可能不会访问两次角色。 – user1929899

“多个方向”是什么意思？单个单词可以使用多个方向，即单词必须是直线还是曲线可以在整个板上？ – meriton

答

一种方法是：

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

要找到所有的路径，你可以适应任何graph traversal algorithm。

现在这将会非常缓慢，因为有一个大小很大的板子的路径（对于有n个单元的板子，我们最多可以有n * 4^(n - 1)路径，所以对于5x5板子，有一些像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; 
     } 
    }

正如你所看到的，方法调用散步本身这种技术被称为recursion

这就为寻找支持有效前缀查询的字典的数据结构留下了一个问题。最好的这种数据结构是Trie。唉，JDK不包含实现，但幸运的是，编写一个并不难。

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

我现在有一个有点类似的递归方法：private void findWord（Woord woord，int positionInWord，Point currentPosition，HashSet visited，StringBuilder currentWoord）{...}，它有效，但有时会给出一些不寻常的结果，没有连接等... – user1929899

答

一个相当简单的概念化方法是对每个位置应用一个breadth-first search（BFS）方法（或深度优先，这取决于您以后可能需要做哪些调整）。这将为您提供所有可能的字母组合，最多可达到与搜索的最大深度相同的字符级别。根据您的要求，例如最长允许的字数，最长运行时间以及通过数据结构或文件提供字典，这可能是关键部分。

或者，您可能需要优化更多。如果是这样，考虑如何加快BFS或DFS。如果你做了一个DFS，但是知道三个字符，那么没有一个字以“zzz”开始？你不需要遍历所有可能的顺序就可以减少很多时间。要有效查看单词，可能需要进一步调整。但是我首先介绍Java的内置功能（在这个例子中想到了String.startsWith（）），测量性能（可能有限的最大字长），然后优化何时何地需要它。要解决这个

答

首先使用简单的重复方法将行，列和对角线转换为字符串。然后，我将它变成一个StringBuilder，或者为了检查哪些单词是真实的，并消除那些不直接来自StringBuilder的单词。然后，只需将其打印到一个String.There有很多有用的工具来消除或替换java中的单词。

来自Java中char数组的字符串的所有可能组合

相关推荐