Java accepted solution for test case ["za","zb","ca","cb"] with explanation


  • 0
    L

    Thanks to the idea from @beckychiu1988 and the fix from @hot13399 to pass ["wrtkj", "wrt"], I'm able to get to the new test case: ["za","zb","ca","cb"]. However in this case an empty string gets returned as result.length() != degree.size(). After debugging for a while, I notice that in the degree map, 'b' is put twice: 1st from "za" and "zb", 2nd from "ca" and "cb", but ideally 'b' should be recorded only once because it's point by the same character. which is 'a'. So the fix is quite simple, just to write down every pair to avoid duplicate input.

    public class Solution {
        public String alienOrder(String[] words) {
            HashMap<Character, HashSet<Character>> map = new HashMap<Character, HashSet<Character>>();
            HashMap<Character, Integer> degree = new HashMap<Character, Integer>();
            HashSet<String> rel = new HashSet<String>();
            
            for(String s : words) {
                for(int i = 0; i < s.length(); i++) {
                    degree.put(s.charAt(i), 0);
                }
            }
            
            for(int i = 0; i < words.length-1; i++) {
                String cur = words[i];
                String next = words[i+1];
                int len = Math.min(cur.length(), next.length());
                for(int j = 0; j < len; j++) {
                    char c1 = cur.charAt(j);
                    char c2 = next.charAt(j);
                    String relation = c1 + "->" + c2;
                    if(c1 != c2) {
                        if(!map.containsKey(c1)) map.put(c1, new HashSet<Character>());
                        map.get(c1).add(c2);
                        
                        if(!rel.contains(relation)) { // this is what I added to record every node to node pair, everything else is same as other's idea
                            degree.put(c2, degree.get(c2)+1);
                            rel.add(relation);
                        }
                        break;
                    }  else {//
                        if(j+1 <= cur.length()-1 && j+1 > next.length()-1) return "";
                    }
                }
            }
            
            Queue<Character> q = new LinkedList<Character>();
            StringBuilder result = new StringBuilder();
            
            for(Character c : degree.keySet()) {
                if(degree.get(c) == 0) q.offer(c);
            }
            
            while(!q.isEmpty()) {
                Character cur = q.poll();
                result.append(String.valueOf(cur));
                
                if(map.containsKey(cur)) {//
                    for(Character neighbor : map.get(cur)) {
                        degree.put(neighbor, degree.get(neighbor)-1);
                        if(degree.get(neighbor) == 0) q.offer(neighbor);
                    }
                }
            }
            
            if(result.length() != degree.size()) return "";
            
            return result.toString();
        }
    }
    

Log in to reply
 

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