Derive Order for New Language

Derive Order for New Language

here's a new language which uses the latin alphabet. However, you don't know the order among letters.

It could be:
a b c d ...

as it could also be:

b e z a m i ...

You receive a list of words lexicographically sorted by the rules of this new language. From this list, derive one valid particular ordering of letters in this language.

Naive Thinking: 这道题是我从来没有见过的类型，想了半天还是想不出来，看了答案，原来是拓扑排序。好厉害呀。

算法复杂度是O(nk) k是平均每个单词的长。从index = 0开始，每次都先找到前一个字母一样的[begin, end]区段，然后调用子函数setOrder(Node[] order, String[] strs, int begin, int end, int index)去连接对应节点，这一部分完成后就得到一个DAG，在DAG上运行拓扑排序得到的顺序就是新语言的顺序。

import java.util.List;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;

public class Solution{
    class Node{
        char val;
        int father;
        List<Node> next;
        Node(char c){
            val = c;
            father = 0;
            next = new ArrayList<Node>();
        }
    }

    public static void main(String args[]){
        Solution s = new Solution();
        String[] strs = {"battle", "bare", "barffdfsdf", "apple", "act", "do", "coap", "cool","copf"};
        //String[] strs = {"battle","bare","apple"};
        s.deriveOrder(strs);
      
    }

    public char[] deriveOrder(String[] strs){
        char[] rlst = new char[26];
        Node[] order = new Node[26];
        for(int i = 0;i < 26;i++)
            order[i] = new Node((char)(i+'a'));
        char preParent = '0', curParent;
        int index = 0;
        boolean hasNext= strs.length!=0;
        while(hasNext){
            int begin = 0, end = 0;
            hasNext = false;
            // find begin word
            while(end < strs.length){
                if(index < strs[end].length()){
                    preParent = index==0?'0':strs[end].charAt(index-1);
                    hasNext = true;
                    break;
                }
                end++;
            }
            // find end word
            begin = end;
            while(++end < strs.length){
                if(index < strs[end].length()){
                    curParent = index==0?'0':strs[end].charAt(index-1);
                    if(curParent!=preParent){
                        setOrder(order,strs,begin,end,index);
                        begin = end;
                        preParent = index==0?'0':strs[begin].charAt(index-1);
                    }
                }
            }
            if(strs[Math.min(end-1,strs.length-1)].length() > index)
                setOrder(order,strs,begin,end,index);
            index++;
        }
      
        // for(int i = 0;i < 26;i++){
        //     System.out.println((char)(i+'a') + " has "+order[i].father+ " fathers with children:");
        //     for(int j = 0;j < order[i].next.size();j++)
        //         System.out.print((char)(order[i].next.get(j).val)+" ");
        //     System.out.println();
        // }

        // topological sort
        Queue<Node> queue = new LinkedList<Node>();
        for(int i = 0;i < 26;i++)
            if (order[i].father==0)
                queue.add(order[i]);
        index = 0;
        while(!queue.isEmpty()){
            Node node = queue.poll();
            rlst[index++] = node.val;
            for(int i = 0;i < node.next.size();i++){
                node.next.get(i).father--;
                if(node.next.get(i).father==0)
                    queue.add(node.next.get(i));
            }
        }

        // for(int i = 0;i < 26;i++)
        //     System.out.print(rlst[i] + " ");

        return rlst;
    }

    private void setOrder(Node[] order, String[] strs, int begin, int end, int index){
        char pre = strs[begin].charAt(index), cur;
        boolean newStart = true;
        for(int i = begin;i < end && i < strs.length;i++){
            if(index < strs[i].length()){
                if(newStart){
                    pre = strs[i].charAt(index);
                    newStart = false;
                }else{
                    cur = strs[i].charAt(index);
                    if(pre!=cur){
                        order[toInt(pre)].next.add(order[toInt(cur)]);
                        order[toInt(cur)].father++;
                        pre = cur;
                    }
                }
            }
        }
    }

    private int toInt(char c){
        return (int)(c-'a');
    }

}


这题太好了，很难找到考拓扑排序的题。