javascript - 基于全路径的层次节点路径生成

Question

我有一个 SQL 查询，它通过连接所有通向根节点的节点返回从叶到节点的完整路径，例如叶“H”是：

H-G-F-E-D-C-B-A 

其中 A 是根节点。这个连接值是叶子 H 的 id，因为它是通向这个叶子并且不会重复的所有节点的组合，路径上的每个节点 id 都是它自己加上它的祖先的连接：

H-G-F-E-D-C-B-A =>LEAF ID
  G-F-E-D-C-B-A
    F-E-D-C-B-A
      E-D-C-B-A
        D-C-B-A
          C-B-A
            B-A
              A => ROOT ID

问题是，我需要一种算法，它可以生成上面列出的所有路径，但只能从 HFEDCBA 之类的字符串开始。所有路径都可以以字符串数组的形式返回，语言可以是 java、python 或 javascript，对于当前的应用程序，我更喜欢 javascript，但任何可以显示算法的语言都可以。

目前这是我在 javascript 中所拥有的：

var text = "";
var array =[];
var i=0;
var j=0;
var pathstring = 'H-G-F-E-D-C-B-A';
var pathleaf = pathstring.split('-');
for (i=0; i< pathleaf.length; i++)
{
 for (j=0; j< pathleaf.length; j++)
 {
 if(j-1>=0)
   array.push(pathleaf[j] +"-"+ pathleaf[j-1]);
 }
 if(i-1>=0){
 text += array[i] +"-"+ array[i-1] + "<br>";
 }
}

测试返回：

F-G-G-H
E-F-F-G
D-E-E-F
C-D-D-E
B-C-C-D
A-B-B-C
G-H-A-B

标签： javascriptjavaalgorithmpython-2.7

Answer 1

这是一种在 Java 中执行此操作的方法，您可能可以适应 Javascript。

static String[] leafIDs(String s)
{
    List<String> sa = new ArrayList<>();
    char[] ca = new char[s.length()];
    for(int j=0, i=s.length()-1; i>=0; i--,j++)
    {
        if((ca[j] = s.charAt(i)) == '-') sa.add(new String(ca, 0, j));
    }
    sa.add(new String(ca));
    return sa.toArray(new String[sa.size()]);
}

或者您可以使用StringBuilder

static String[] leafIDsSB(String s)
{
    List<String> sa = new ArrayList<>();
    StringBuilder b = new StringBuilder();
    for(int i=s.length()-1; i>=0; i--)
    {
        char c = s.charAt(i);
        if(c == '-') sa.add(b.toString());
        b.append(c);
    }
    sa.add(b.toString());
    return sa.toArray(new String[sa.size()]);
}

测试

public static void main(String[] args)
{
    for(String so : leafIDs("H-G-F-E-D-C-B-A")) System.out.println(so); 
}   

输出：

A
A-B
A-B-C
A-B-C-D
A-B-C-D-E
A-B-C-D-E-F
A-B-C-D-E-F-G
A-B-C-D-E-F-G-H