My accepted Java solution


  • 0
    Z
    public String alienOrder(String[] words) {
        int[] chars = getChar(words);
        HashMap<Character,ArrayList<Character>> adj = build(words,chars);
        return topological(adj,chars);
    }
    public String topological(HashMap<Character,ArrayList<Character>> adj,int[] chars){
        Stack<Character> st = new Stack<Character>();
        boolean visited[] = new boolean[26];
        for(char ch:adj.keySet()){
            if(!visited[ch-'a'] && !DFS(ch,adj,st,visited,new HashSet<Character>())){
                return "";
            }
        }
        String s = "";
        while(!st.isEmpty()) s += st.pop();
        // characters have not occured in any edges. just append them to the result
        for(int i=0;i<26;i++){
            if(chars[i] == 1){
                s += (char)('a'+i);
            }
        }
        return s;
    }
    public boolean DFS(char c,HashMap<Character,ArrayList<Character>> adj,Stack<Character> st,boolean[] visited,HashSet<Character> set){
        visited[c-'a'] = true;
        if(!adj.containsKey(c)){
            st.push(c);
            return true;
        } 
        set.add(c);
        for(char x:adj.get(c)){
            if(set.contains(x)) return false;
            if(!visited[x-'a'] && !DFS(x,adj,st,visited,set)){
                return false;
            }
        }
        set.remove(c);
        st.push(c);
        return true;
    }
    // get all chars that occured in words
    public int[] getChar(String[] words){
        int[] chars = new int[26];
        for(String s:words){
            for(int i=0;i<s.length();i++){
                chars[s.charAt(i)-'a'] = 1;
            }
        }
        return chars;
    }
    //create the adjacent list
    public HashMap build(String[] words,int[] chars){
        HashMap<Character,ArrayList<Character>> adj = new HashMap<Character,ArrayList<Character>>();
        for(int i=0;i<words.length;i++){
            for(int j=i+1;j<words.length;j++){
                buildAdjList(words[i],words[j],adj,chars);
            }
        }
        return adj;
    }
    public void buildAdjList(String a,String b,HashMap<Character,ArrayList<Character>> adj,int[] chars){
        for(int i=0,j=0;i<a.length()&&j<b.length();i++,j++){
            if(a.charAt(i) != b.charAt(j) ){
                // unmark chars that have occured in any edges
                chars[a.charAt(i)-'a'] = 0;
                chars[b.charAt(j)-'a'] = 0;
                if(!adj.containsKey(a.charAt(i))) {
                    adj.put(a.charAt(i),new ArrayList<Character>());
                }
                adj.get(a.charAt(i)).add(b.charAt(j));
                break;
            }
        }
    }

  • 0
    F

    public class Solution {
    //26 letters
    public static int N = 26;

    public String alienOrder(String[] words) {
        if(words == null || words.length == 0) return "";
        if(words.length == 1) return words[0];
        
        //the dependence relationship N*N array.
        boolean[][] dependence = new boolean[N][N];
        //indegree for every letter
        int[] indegree = new int[N];
        //existence
        boolean[] existence = new boolean[N];
        
        for(int i = 0; i < words.length; ++i){
            if(words[i] == null) continue;
            for(int j = 0; j < words[i].length(); ++j){
                //set existence
                existence[words[i].charAt(j)-'a'] = true;
            }
            if(i >= 1) checkTwoStrings(words[i-1], words[i], dependence, indegree);
        }
        
        return toplogical_sort(dependence, indegree, existence);
    }
    
    public String toplogical_sort(boolean[][] dependence, int[] indegree, boolean[] existence){
        //queue used to store those whose indegree = 0
        Queue<Integer> q = new LinkedList<Integer>();
        //result
        StringBuilder res = new StringBuilder();
        
        for(int i = 0; i < N; ++i){
            if(indegree[i] == 0 && existence[i]) q.add(i);
        }
        
        while(!q.isEmpty()){
            int poll = q.poll();
            res.append((char)(poll+'a'));
            for(int i = 0; i < N; ++i){
                if(dependence[i][poll] == true) {
                    indegree[i] -= 1;
                    if(indegree[i] == 0) q.add(i);
                }
            }
        }
        
        for(int i = 0; i < N; ++i){
            if(indegree[i] != 0) return "";
        }
        return res.toString();
    }
    
    public void checkTwoStrings(String s1, String s2, boolean[][] dependence, int[] indegree){
        int minlen = Math.min(s1.length(), s2.length());
        for(int i = 0; i < minlen; ++i){
            if(s1.charAt(i) != s2.charAt(i) && 
                dependence[s2.charAt(i)-'a'][s1.charAt(i)-'a'] == false){
                dependence[s2.charAt(i)-'a'][s1.charAt(i)-'a'] = true;
                indegree[s2.charAt(i) - 'a'] += 1;
                break;
            }
        }
    }
    

    }


  • 0

    what would be the Big-O of this solution in terms of time?


  • 0
    Z

    To build the adjacent list,the time complexity is at most O(nnlen). where n is number of words and len is the average length of each word. To get all characters that occur in all words, the time complexity is O(nlen). The topological sort take O(V+E),where V is number of vertex in adjacent list and E is number of edge. So the complexity is O(nn*len)


Log in to reply
 

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