1

我正在研究一种算法来查找图中两个节点之间的所有路径。就是这样，我能够对字符串数组中的所有路径进行编码，如下所示：

String []paths = new String[50];

注意：我使用字符串数组来存储路径，但我可以在必要时将它们存储在任何其他数据结构中。

我的数组中的数据示例如下表所示，请注意，字母是我的数据，连字符仅用于可视化：

 -----------
| A | B | C |
 -----------
| D | E |   |
 -----------

我只需要处理上述数组，并将所有组合输出为：

ABC

AEC

DBC

DEC

我尝试使用迭代方法“循环”来解决这个问题，但我失败了。我认为我们可以通过递归来做到这一点，但我不知道该怎么做。另外，我不知道是否有任何数据结构可以解决这个问题。存储路径而不是字符串数组更好的方法？

无论如何，这是我正在处理的循环：

String []temp = new String[100];
for( r=0; r<paths.length ;r++ )
   for( c=0; c<paths[r].length() ;c++ )
      for( j=c+1; j<paths[r].length() ;j+1 )
         temp[r] += paths[j];
4

1 回答 1

1

所以正则表达式[AD][BE][C]。

这也是一个更好的数据结构：数组旋转 90 度。这将消除检查长度（ABC 与 DE）。

尽管如此，对于您的数据结构：

int maxPathLength = 3; // TODO calculate
Set<String> results = new TreeSet<String>();
process(paths, "", 0);

public void process(String[] paths, String prefix, int i, Set<String> results) {
    if (i >= maxPathLength) {
        System.out.println(prefix);
        results.add(prefix);
        return;
    }
    for (String s : paths) {
         if (i < s.length()) {
             process(paths, prefix + s.charAt(i), i + 1, results);
         }
    }
}
于 2012-12-15T04:10:29.773 回答