Нахождение приоритета символов в словаре

Question

** Учитывая словарь строк [строки в отсортированном порядке] вы должны найти приоритет символов согласно словарю ..

ест
Ъха

е оценивается выше Ь согласно словарю! **

Я пытался решить этот вопрос с топологической сортировкой и написал следующий код, он дал мне выход ebxyat. Я не мог быть уверен в моем решении, каких-либо предложениях? (Этот вопрос был задан в интервью 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); 

     }   
    } 
} 

Answer 1

Да. Если бы вы дали 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 

Все перестановки {т, а, к, е, b, x, y} с t до e, e до b и y до того, как x будет действительным решением. И топсорт даст один из них.