Java AC solution, Topological sort


  • 0
    W

    The idea is to use topological sort.
    basically find the first char with idx i that is different in two word w1, w2, generate a rule w1[i] -> w2[i]. Iterate the whole array to generate rules and use standard topological sort algorithm to sort the rules.

    public class Solution {
        public String alienOrder(String[] words) {
            Map<Character, Set<Character>> map = new HashMap<>();
            Map<Character, Integer> inverseMap = new HashMap<>();
            Set<Character> set = new HashSet<>();
            for (int i=0; i<words.length-1; i++) {
                int m=0;
                for (char c: words[i].toCharArray()) set.add(c);
                while(m < words[i].length() && m < words[i+1].length()) {
                    char c1 = words[i].charAt(m);
                    char c2 = words[i+1].charAt(m);
                    if (c1 != c2) {
                        if (!map.containsKey(c1))
                            map.put(c1, new HashSet<>());
                        if (map.get(c1).add(c2)) {
                            if (!inverseMap.containsKey(c2))
                                inverseMap.put(c2, 1);
                            else
                                inverseMap.put(c2, inverseMap.get(c2)+1);
                        }
                        break;
                    }
                    m++;
                }
                if (m == words[i+1].length() && words[i].length() > m) return "";
            }
            for (char c: words[words.length-1].toCharArray()) set.add(c);
            
            Deque<Character> q = new ArrayDeque<>();
            StringBuilder sb = new StringBuilder();
            for (char c: set) {
                if (!inverseMap.containsKey(c))
                    q.offer(c);
            }
            
            while(!q.isEmpty()) {
                char c1 = q.poll();
                sb.append(c1);
                if (map.containsKey(c1)) {
                    for (char c2: map.get(c1)) {
                        if (inverseMap.get(c2) == 1)
                            q.offer(c2);
                        inverseMap.put(c2, inverseMap.get(c2)-1);
                    }
                }
            }
            return sb.length() == set.size() ? sb.toString() : ""; 
        }
    }
    

Log in to reply
 

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