Java AC solution using BFS


  • 124
    B
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> map=new HashMap<Character, Set<Character>>();
        Map<Character, Integer> degree=new HashMap<Character, Integer>();
        String result="";
        if(words==null || words.length==0) return result;
        for(String s: words){
            for(char c: s.toCharArray()){
                degree.put(c,0);
            }
        }
        for(int i=0; i<words.length-1; i++){
            String cur=words[i];
            String next=words[i+1];
            int length=Math.min(cur.length(), next.length());
            for(int j=0; j<length; j++){
                char c1=cur.charAt(j);
                char c2=next.charAt(j);
                if(c1!=c2){
                    Set<Character> set=new HashSet<Character>();
                    if(map.containsKey(c1)) set=map.get(c1);
                    if(!set.contains(c2)){
                        set.add(c2);
                        map.put(c1, set);
                        degree.put(c2, degree.get(c2)+1);
                    }
                    break;
                }
            }
        }
        Queue<Character> q=new LinkedList<Character>();
        for(char c: degree.keySet()){
            if(degree.get(c)==0) q.add(c);
        }
        while(!q.isEmpty()){
            char c=q.remove();
            result+=c;
            if(map.containsKey(c)){
                for(char c2: map.get(c)){
                    degree.put(c2,degree.get(c2)-1);
                    if(degree.get(c2)==0) q.add(c2);
                }
            }
        }
        if(result.length()!=degree.size()) return "";
        return result;
    }

  • 0
    D

    This method is actually easier to understand and study than the traditional topological approach.


  • 8
    B

    Thanks~ I met this problem in my onsite interview.


  • 0
    J

    for Google interview?


  • 4
    B

    No. Pocket gems.


  • 0
    C

    Hi, can you talk about the time complexity of your algorithm?


  • 0
    W

    thanks for this straightforward answer


  • 1
    C

    Could you please run through your solution ?


  • 98
    Y

    Really nice solution! Let me try to explain the code with example in the problem description:

    First, build a degree map for each character in all the words:

    w:0
    r:0
    t:0
    f:0
    e:0
    

    Then build the hashmap by comparing the adjacent words, the first character that is different between two adjacent words reflect the lexicographical order. For example:

     "wrt",
     "wrf",
        first different character is 3rd letter, so t comes before f
    
     "wrf",
     "er",
        first different character is 1rd letter, so w comes before e
    

    The characters in set come after the key. x->y means letter x comes before letter y. x -> set: y,z,t,w means x comes before all the letters in the set. The final HashMap "map" looks like.

    t -> set: f    
    w -> set: e
    r -> set: t
    e -> set: r
    

    and final HashMap "degree" looks like, the number means "how many letters come before the key":

    w:0
    r:1
    t:1
    f:1
    e:1
    

    Then use Kahn's aglorithm to do topological sort. This is essentially BFS.
    https://en.wikipedia.org/wiki/Topological_sorting


  • 0
    J

    Thank you so much for great answer~


  • 0
    B

    Yes! That's exactly how it works! Thank you for helping me explain it for others!


  • 0
    X

    Seems the time complexity is O(m*n)?


  • 0
    M

    Why is just looking at two adjacent words sufficient? Why not compare every pair of words?


  • 1
    Y

    @mangoyogurt, because only from adjacent two words can you tell the immediate order of letters. A counter example, In the problem description, first word is wrt, last word is rftt, if compare this pair, we know that r is after w, but r may not IMMEDIATELY after w.


  • 0
    B

    May you explain why is it that we know that "r may not IMMEDIATELY after w"? What's special about comparing only adjacent words vs comparing all words after a certain word?


  • 0
    B

    May you explain why we only compare adjacent words? What's special about comparing only adjacent words vs comparing with all words after a certain word?


  • 2
    W

    I am sorry ,can you explain if(result.length()!=degree.size()) return ""; ?


  • 0
    B

    Wow, this problem is a beast! Building the graph can be a bit of a nightmare.Nice solution! @www2277843987 the last check is to ensure that all letters have been used. The degrees contains all the characters in all the words. If the result size is different then a character has been left out and the letters can't be arranged lexicographically.


  • 5

    First of all, your solution is great and easy understanding, I just modify the HashMap degree by changing from HashMap to int[26], and add a HashSet to save all letters which are used. I think this version is a little bit faster than yours. Here is the code:

    public String alienOrder(String[] words) {
            if(words == null || words.length == 0) return "";
            Map<Character, Set<Character>> dependency = new HashMap<>();
            int[] degree = new int[26];
            Set<Character> dict = new HashSet<>(); 
            StringBuilder sb = new StringBuilder();
    
    
            // save all characters which is used in the hash set
            for(String word: words) {
                for(char c: word.toCharArray()) {
                    dict.add(c);
                }
            }
    
            // build dependency graph
            for(int i=0; i<words.length-1; i++) {
                char[] w1 = words[i].toCharArray(), w2 = words[i+1].toCharArray();
                int len = Math.min(w1.length, w2.length);
                for(int j=0; j<len; j++) {
                    char c1 = w1[j], c2 = w2[j];
                    if(c1 == c2) continue;
    
                    Set<Character> c2Set = dependency.containsKey(c1) ? dependency.get(c1) : new HashSet<>();
                    if(!c2Set.contains(c2)) {       // avoid duplicates
                        c2Set.add(c2);
                        dependency.put(c1, c2Set);
                        degree[c2 - 'a']++;
                        break;
                    }
                }
            }
    
            // insert the nodes which have no parents
            Queue<Character> queue = new LinkedList<>();
            for(char c: dict) {
                if(degree[c - 'a'] == 0) queue.add(c);
            }
            
            // BFS search
            while(!queue.isEmpty()) {
                char c1 = queue.poll();
                sb.append(c1);
                if(!dependency.containsKey(c1)) continue;
                for(char c2: dependency.get(c1)) {
                    // decrease the degree, and insert the new nodes which have no parents now
                    if(--degree[c2 - 'a'] == 0) queue.add(c2);
                }
            }
    
            // avoid the loop
            if(sb.length() != dict.size()) return "";
            return sb.toString();
        }
    

  • 3
    S

    "["za","zb","ca","cb"]" How is this test case handled. It should give out an empty string as the order can not be decided from the words given. but instead it returns "azbc".

    Can someone please explain this.

    Thanks!


Log in to reply
 

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