Problem breakdown 9ms java solution with some explaination


  • 0
    Q

    The problem can be treated as a topology sort problem, since in topology sort, the result is the list that from root to leaf in order.
    There are several components in topology sort model.

    1. we need to find all the vertices
    2. we need to find all the edges
    3. build the directed graph
    4. build the order

    There are several special cases here.

    1. if there is cycle, for example, ["a", "b", "a"] . There is not valid order, should return "".
    2. if the next word is the prefix of the current word ["ab", "a" ], it's not valid either
    3. if the order can't be found, and it's still valid dictionary, for example ["ab", "ab"], both"ab", "ba" are valid results.
    public String alienOrder(String[] words) {
        int n = words.length;
        if(n == 0) return "";
        List<char[]> edges = new ArrayList();
        // get all chars appeared
        Set<Character> set = new HashSet<Character>();
        for(int i = 0; i < n ; i++){
            for(char c : words[i].toCharArray()){
                if(!set.contains(c)){
                    set.add(c);
                }
            }
        }
        
        // build edge
        for(int i = 0; i < n -1 ; i++){
            if(words[i].equals(words[i+1])) continue;
            char[] edge = getEdge(words[i], words[i+1]);
            // special case #2
            if(edge[0] == '*') return "";
            if(edge[0] == '\u0000') continue;
            edges.add(edge);
        }
        
        List<Integer>[] graph = new ArrayList[26];
        int[] indegrees = new int[26];
        
        // build graph
        for(char[] edge : edges){
            if(graph[edge[0] -'a'] == null){
                graph[edge[0] -'a'] = new ArrayList();
            }
            graph[edge[0] -'a'].add(edge[1] -'a');
            indegrees[edge[1] -'a']++;
        }
        
        // topology sort
        Queue<Integer> q = new LinkedList();
        for(char i : set){
            if(indegrees[i-'a'] == 0){
                q.offer(i-'a');
            }
        }
        char[] orders = new char[set.size()];
        int pos = 0;
        while(!q.isEmpty()){
            Integer cur = q.poll();
            orders[pos] = (char)(cur + 'a');
            pos++;
            
            if(graph[cur] != null){
                for(Integer nb : graph[cur]){
                    indegrees[nb]--;
                    if(indegrees[nb] == 0){
                        q.offer(nb);
                    }
                }
            }
        }
        // check cycle
        if(edges.size() != 0 && pos != set.size()) return "";
        StringBuilder rt = new StringBuilder();
        for(char c : orders){
            if(c == '\u0000') continue;
            rt.append(c);
        }
        return rt.toString();
    }
    
    char[] getEdge(String s, String l){
        int len1 = s.length();
        int len2 = l.length();
        char[] edge = new char[2];
        for(int i = 0; i< len1 && i < len2;i++){
            if(s.charAt(i) == l.charAt(i))
                continue;
            else
            {
                edge[0] = s.charAt(i);
                edge[1] = l.charAt(i);
                return edge;
            }
        }
        if(len1 > len2){
            edge[0] = '*';
        }
        return edge;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.