java - 查找字典中字符的优先级

Question

**给定一个字符串字典[字符串按排序]你必须根据字典找到字符的优先级..

eat
bxy

根据字典，e排在b之上!**

我尝试用拓扑排序解决这个问题并编写了以下代码，它给了我 e-b-x-y-a-t 的输出。我不确定我的解决方案，有什么建议吗？ (这个问题是在谷歌面试中问到的)

  public static ArrayList<Vertex> topologicalSort (List<Vertex> graph){

    if (graph == null || graph.isEmpty()){
        throw new IllegalArgumentException();
    }

    ArrayList<Vertex> result = new ArrayList<>(); 

    for (Vertex v : graph){
        if (!v.isVisited){
            dfs(v,result);
        }
    }
    return result;      
}

public static void dfs (Vertex v, ArrayList<Vertex> result){

    v.isVisited = true;

    for (Vertex adjVertex : v.AdjList){
        if (!adjVertex.isVisited){
            dfs(adjVertex, result);
        }
    }
    result.add(v);      
}

     public static void main(String[] args) {
      List<Vertex> graph = new ArrayList<>();

        Vertex p1 = new Vertex("e");
        Vertex p2 = new Vertex("a");
        Vertex p3 = new Vertex("t");
        Vertex p4 = new Vertex("b");
        Vertex p5 = new Vertex("x");
        Vertex p6 = new Vertex("y");

        p1.AdjList = Arrays.asList(new Vertex[]{p2, p4});
        p2.AdjList = Arrays.asList(new Vertex[]{p3});
        p3.AdjList = Arrays.asList(new Vertex[]{});
        p4.AdjList = Arrays.asList(new Vertex[]{p5});
        p5.AdjList = Arrays.asList(new Vertex[]{p6});
        p6.AdjList = Arrays.asList(new Vertex[]{});

        graph.add(p1);
        graph.add(p2);
        graph.add(p3);
        graph.add(p4);
        graph.add(p5);
        graph.add(p6);

        ArrayList<Vertex> compileOrder = topologicalSort(graph);

        for( Vertex vertex : compileOrder){
        System.out.println(vertex.data );

        }           
    }
}   

Answer 1

是的。如果您给出 Top-Sort 作为答案，那将是正确的。在给定的示例中，您只有 2 个单词。因此，您可以确定的一件事是字典中的 e 在 b 之前。您无法确定其他字符。在示例中，您有 6 个字符。

实际上，这 6 个字符的每个排列都是有效的输出，唯一的限制是 e 放在 b 之前。所以，这个例子有 !6/2 或 360 个正确的解决方案。

对于更大的数据集，您的顶级排序会起作用，我认为这是一个有效的解决方案。

例如，您有 4 个字符串:

tak, eat, byx, bxy

那么，你唯一确定的关系是:

t>e, e>b, y>x

{t,a,k,e,b,x,y} 的所有排列，t 在 e 之前，e 在 b 之前，y 在 x 之前，都是有效的解决方案。 topsort 将给出其中之一。