DFS Java EASY solution


  • 2
    public class Solution {
        public String alienOrder(String[] words) {
            boolean[][] edges = new boolean[26][26];
            int[] status = new int[26]; //not exists - 0; unvisited - 1; visiting - 2; visited - 3
            for(String str : words){
                char[] c_arr = str.toCharArray();
                for(char c : c_arr){
                    status[c - 'a'] = 1;
                }
            }
            
            for(int i = 0; i < words.length - 1; i++){
                char[] str1 = words[i].toCharArray();
                char[] str2 = words[i + 1].toCharArray();
                int len = Math.min(str1.length, str2. length);
                int j = 0;
                for(j = 0; j < len; j++){
                    if(str1[j] != str2[j]){
                        edges[str1[j] - 'a'][str2[j] - 'a'] = true;
                        break;
                    }
                }
                if(j == len && str1.length > len){
                    return ""; //"abcd" before "abc" is wrong. space should be before any letter.
                }
            }
            
            StringBuilder res = new StringBuilder();
            for(int i = 0; i < status.length; i++){
                if(status[i] == 1){
                    if(!dfs(i, edges, status, res)){
                        return "";
                    }
                }
            }
            return res.reverse().toString();
        }
        
        public boolean dfs(int start, boolean[][] edges, int[] status, StringBuilder res){
            status[start] = 2;
            for(int i = 0; i < 26; i++){
                if(edges[start][i]){
                    if(status[i] == 2){
                        return false; //cycle
                    }
                    if(status[i] == 1){
                        if(!dfs(i, edges, status, res)){
                            return false;
                        }
                    }
                }
            }
            status[start] = 3;
            res.append(String.valueOf((char)(start+'a')));
            return true;
        }
    }
    

Log in to reply
 

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