Java Accepted Solution


  • 0
    M

    I referred all the best answers and tried hard to get accepted solution.
    Thank you all for your brilliance.
    I learned a lot from gifted people.
    Here is my answer to help others too.

    1. run DFS and list vertex on ending time in reverse order
    int[][] graph = new int[26][26];
    int[] status = new int[26];
    
    public String alienOrder(String[] words) {
        buildGraph(words);
    
        StringBuilder sb = new StringBuilder();
        char v=' ';
        
        for(int i=0;i<status.length;i++){
            if(status[i]==1){
                v = (char)(i+'a');
                if(!runDFS(v, sb)) return "";
            } 
        }
        return sb.reverse().toString();
        
    }
    private boolean runDFS(char v, StringBuilder sb){
        if(status[v-'a']==2) return false; // detect back edge
        if(status[v-'a']==3) return true;  // detect cross edge
        
        status[v-'a'] = 2; // discoverd
        
        // check neighbors of vertex v
        for(int i=0;i<26;i++){
            if(graph[v-'a'][i]==1){
                if(!runDFS((char)(i+'a'), sb)) return false;
            }
        }
        status[v-'a']=3; //finished
        sb.append(v);
        return true;
    }
    private void buildGraph(String[] words){
        for(int i=0;i<words.length;i++){
            for(int j=0;j<words[i].length();j++){
                // vertice.
                status[words[i].charAt(j)-'a']=1;
            }
        }
        for(int i=0;i<words.length-1;i++){
            int min = Math.min(words[i].length(), words[i+1].length());
            for(int p=0;p<min;p++){
                char c1 = words[i].charAt(p);
                char c2 = words[i+1].charAt(p);
                
                if(c1!=c2){
                    //build a graph c1->c2
                    graph[c1-'a'][c2-'a'] = 1;
                    break;
                }
            }
        }
    }
    
    
    2. finding vertex with no incoming edges
    
    
    int[] indegree = new int[26];
    int[] vertex = new int[26];
    int[][] graph = new int[26][26];
    public String alienOrder(String[] words) {
        buildGraph(words);
        
        Queue<Integer> que = new LinkedList<>();
        for(int i=0;i<26;i++){
            if(vertex[i]==1 && indegree[i]==0)
                que.add(i);
        }
        int totVertex = 0;
        for(int i=0;i<26;i++){
            if(vertex[i]==1) totVertex++;
        }
        StringBuilder sb = new StringBuilder();
        while(!que.isEmpty()){
            int v = (int)que.poll();
            sb.append((char)(v+'a'));
            for(int i=0;i<26;i++){
                if(graph[v][i]==1 && indegree[i]>0){
                    if(--indegree[i]==0){
                        que.add(i);
                    }
                }
            }
        }
    
        return sb.length()==totVertex?sb.toString():"";
    }
    
    private void buildGraph(String[] words){
        // check vertex
        for(String word : words){
            for(int i=0;i<word.length();i++){
                vertex[word.charAt(i)-'a']=1;
            }
        }
        // build a graph
        for(int i=0;i<words.length-1;i++){
            int min = Math.min(words[i].length(), words[i+1].length());
            for(int p=0;p<min;p++){
                char c1 = words[i].charAt(p);
                char c2 = words[i+1].charAt(p);
                if(c1!=c2){
                    //build a graph c1->c2
                    if(graph[c1-'a'][c2-'a']==0){ 
                        graph[c1-'a'][c2-'a']=1;
                        indegree[c2-'a']++;  // increase incoming edges.
                    }
                    break;
                }
            }
        }
        
    }

Log in to reply
 

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