2015-10-09 64 views
3

**給出一個字符串詞典[字符串都在有序]你必須要找到根據字典字符的優先級..查找字符的優先級在字典


BXY

e爲根據字典上面的排名b!**

我試圖解決這個問題,用拓撲排序,並寫了下面的代碼,它給了我ebxyat的輸出。我無法確定我的解決方案,有什麼建議嗎? (這個問題在谷歌接受採訪時問)

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

     }   
    } 
} 
+1

我不明白「優先級」是什麼意思。例如,與e和b相關的排名如何?你的意思是他們第一次出現的順序? –

+0

我覺得按照字典的順序。 –

+1

e的排名高於a,並且a的排名高於t,基本上是它們出現的順序。 –

回答

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,A,K,E的所有排列, b,x,y}在e之前有t,e在b之前,y在x之前是一個有效的解。並且topsort將給那些之一。