首页 文章

查找字典中字符的优先级

提问于
浏览 次
3

**给定字符串字典[字符串按排序顺序]，您必须根据字典查找字符的优先级 .

吃bxy

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

我尝试用拓扑排序解决这个问题，并编写了下面的代码，它给了我一个e-b-x-y-a-t的输出 . 我无法确定我的解决方案，有什么建议吗？ （这个问题在Google采访中被问到）

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 );

        }           
    }
}
java algorithm dictionary data-structures topological-sort

1 回答

  • 2

    是 . 如果你给Top-Sort作为答案，那就是对的 . 在给定的示例中，您只有2个单词 . 所以，你可以确定的一件事是字典中的 e is before b . 你无法确定其他角色 . 在该示例中，您有6个字符 .

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

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

    比方说，例如，你有4个字符串：

    tak, eat, byx, bxy

    那么，你唯一的关系是：

    t>e, e>b, y>x

    在t之前具有t的{t，a，k，e，b，x，y}的所有排列在x之前的b和y之前将是有效解 . 并且topsort会给出其中一个 .

    回复于

相关问题