Beats 98%, 2ms Java DFS Solution without using StringBuilder or stack,


  • 2
    V

    Let me know if you didn't understand the solution.

        public String alienOrder(String[] words) {
            boolean[][] graph = new boolean[26][26];
            int[] status = new int[26];
            int[] count = {0};
            char[] result = new char[26]; // what ever the topological sort is, path length will not be greater than 26;
            buildGraph(words,graph,status);
            for(int i = 0 ; i < 26 ; i++){
                if(status[i] == 1 && !DFS(i, graph, status,result,count)){
                    return "";
                }
            }
            return new String(result,0,count[0]);
        }
        
        private boolean DFS(int index, boolean[][] graph, int[] status, char[] result, int[] count){
            if(status[index] == 2) return false;
            status[index] = 2;
            for(int i = 0 ; i < 26 ; i++){
                if(graph[index][i] && status[i] != 3 && !DFS(i, graph,status,result,count)){
                    return false;
                }
            }
            status[index] = 3;
            result[count[0]++] = (char) (index + 'a');
            return true;
        }
        
        private void buildGraph(String[] words,boolean[][] graph, int[] status){
            for(int i = 0 ; i < words.length ; i++){
                for(char letter : words[i].toCharArray()) status[letter - 'a'] = 1;
                if(i > 0){
                    String w1 = words[i], w2 = words[i-1]; // w2 is greater
                    int min = Math.min(w1.length(),w2.length());
                    for(int j = 0 ; j < min ; j++){
                        char c1 = w1.charAt(j), c2 = w2.charAt(j); 
                        if( c1 != c2){
                            graph[c1-'a'][c2-'a'] = true; // it means c1 will appear before c2.
                            break;
                        }
                    }
                }
            }
        }
    

  • 0

    I used to build the graph using the radix-sort-like way, but from your post I found just comparing 2 adjacent words is more intuitive and easier to implement. Thanks!


Log in to reply
 

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