Given a sorted dictionary of an alien language, find order of characters | GeeksforGeeks

Given a sorted dictionary of an alien language, find order of characters | GeeksforGeeks
Given a sorted dictionary (array of words) of an alien language, find order of characters in the language.
Examples:

Input:  words[] = {"baa", "abcd", "abca", "cab", "cad"}  

Output: Order of characters is 'b', 'd', 'a', 'c'

The idea is to create a graph of characters and then find topological sorting of the created graph. Following are the detailed steps.

1) Create a graph g with number of vertices equal to the size of alphabet in the given alien language. For example, if the alphabet size is 5, then there can be 5 characters in words. Initially there are no edges in graph.

2) Do following for every pair of adjacent words in given sorted array.
…..a) Let the current pair of words be word1 and word2. One by one compare characters of both words and find the first mismatching characters.
…..b) Create an edge in g from mismatching character of word1 to that of word2.

3) Print topological sorting of the above created graph.

// A recursive function used by topologicalSort

void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack)

{

    // Mark the current node as visited.

    visited[v] = true;

    // Recur for all the vertices adjacent to this vertex

    list<int>::iterator i;

    for (i = adj[v].begin(); i != adj[v].end(); ++i)

        if (!visited[*i])

            topologicalSortUtil(*i, visited, Stack);

    // Push current vertex to stack which stores result

    Stack.push(v);

}

// The function to do Topological Sort. It uses recursive topologicalSortUtil()

void Graph::topologicalSort()

{

    stack<int> Stack;

    // Mark all the vertices as not visited

    bool *visited = new bool[V];

    for (int i = 0; i < V; i++)

        visited[i] = false;

    // Call the recursive helper function to store Topological Sort

    // starting from all vertices one by one

    for (int i = 0; i < V; i++)

        if (visited[i] == false)

            topologicalSortUtil(i, visited, Stack);

    // Print contents of stack

    while (Stack.empty() == false)

    {

        cout << (char) ('a' + Stack.top()) << " ";

        Stack.pop();

    }

}

int min(int x, int y)

{

    return (x < y)? x : y;

}

// This function fidns and prints order of characer from a sorted

// array of words. n is size of words[].  alpha is set of possible

// alphabets.

// For simplicity, this function is written in a way that only

// first 'alpha' characters can be there in words array.  For

// example if alpha is 7, then words[] should have only 'a', 'b',

// 'c' 'd', 'e', 'f', 'g'

void printOrder(string words[], int n, int alpha)

{

    // Create a graph with 'aplha' edges

    Graph g(alpha);

    // Process all adjacent pairs of words and create a graph

    for (int i = 0; i < n-1; i++)

    {

        // Take the current two words and find the first mismatching

        // character

        string word1 = words[i], word2 = words[i+1];

        for (int j = 0; j < min(word1.length(), word2.length()); j++)

        {

            // If we find a mismatching character, then add an edge

            // from character of word1 to that of word2

            if (word1[j] != word2[j])

            {

                g.addEdge(word1[j]-'a', word2[j]-'a');

                break;

            }

        }

    }

    // Print topological sort of the above created graph

    g.topologicalSort();

}

https://xiangcaohello.wordpress.com/2014/07/08/given-a-dictionary-of-strings-strings-are-in-sorted-order-find-the-precedence-of-characters-according-to-the-dictionary/
建立DAG的时候可以用3-WAY SORT 优化。 3 way sort的好处就是减少字母与字母之间的比较.
http://blueocean-penn.blogspot.com/2015/01/given-sorted-dictionary-find-precedence.html

public static class CNode {

char c;

Set<CNode> outgoing = new HashSet<CNode>();

CNode(char i){this.c=i;}

  //these two methods are important for hash
  //but we are not using them in this solution

public int hasCode() {return this.c;}

public boolean equals(Object c) {

if(c == this)

return true;

if(c instanceof CNode){
return this.c == ((CNode)c).c;
}
return false;

}

}

public static List<Character> findLanguageOrderDFS(String[] words){

Set<CNode> vertices = new HashSet<CNode>();

createGraph(words, vertices);

List<Character> result = new ArrayList<Character>();

//add those vertices without any incoming edges

Set<CNode> visited = new HashSet<CNode>();

Set<CNode> processed = new HashSet<CNode>();

Stack<CNode> stack = new Stack<CNode>();

for(CNode n : vertices){

if(visited.contains(n))

     continue;

   if(processed.contains(n))

     throw new IllegalArgumentException("cycle found");

DFS(n, visited, processed, stack);

visited.add(n);

stack.add(n);

}

while(!stack.isEmpty()){

result.add(stack.pop().c);

}

return result;

}

public static void DFS(CNode v, Set<CNode> visited,  Set<CNode> processed, Stack<CNode> s){

if(visited.contains(v))

return;

if(processed.contains(v))

throw new IllegalArgumentException("cycle found");

processed.add(v);

for(CNode n : v.outgoing){

if(!visited.contains(n)){

DFS(n, visited, processed, s);

}

}

visited.add(v);

s.push(v);

}

private static void createGraph(String[] words,

Set<CNode> vertices) {
//we may not need this hash map if we can trust the hashcode() written in CNode class

Map<Character, CNode> nodes = new HashMap<Character, CNode>();

for(int i=0; i<words.length-1; i++){

String current = words[i], next = words[i+1];

int j = 0;

for(j=0; j<current.length() && j<next.length() && current.charAt(j) == next.charAt(j); j++){}

char c1=current.charAt(j), c2=next.charAt(j);

CNode start = null, end = null;

if(!nodes.containsKey(c1)){

start = new CNode(c1);

nodes.put(c1, start);

vertices.add(start);

}

if(!nodes.containsKey(c2)){

end = new CNode(c2);

nodes.put(c2, end);

vertices.add(end);

}

start = nodes.get(c1);

end = nodes.get(c2);

start.outgoing.add(end);

}

}

Iterative Version: https://theetaone.wordpress.com/2014/08/17/alien-language-dictionary-problem/

Read full article from Given a sorted dictionary of an alien language, find order of characters | GeeksforGeeks