BFS from baozi


  • 0
    W
    public class Solution {
        public String alienOrder(String[] words) {
            if(words == null || words.length == 0) return "";
            if(words.length == 1) return words[0];
            Map<Character, Set<Character>> map = new HashMap<>();
            buildGraph(words, map);
            StringBuilder sb = new StringBuilder();
            topological(map, sb);
            return sb.length() == 0 ? "" : sb.toString();
        }
        
        private void buildGraph(String[] words, Map<Character, Set<Character>> map) {
            String s1 = words[0];
            for(int i = 1; i < words.length; i++) {
                String s2 = words[i];
                add(s1, s2, map);
                s1 = s2;
            }
        }
        
        private void add(String s1, String s2, Map<Character, Set<Character>> map) {
            int i = 0; 
            int j = 0;
            while(i < s1.length() && j < s2.length()) {
                char c1 = s1.charAt(i);
                char c2 = s2.charAt(j);
                if(!map.containsKey(c1)) {
                    map.put(c1, new HashSet<>());
                }
                if(!map.containsKey(c2)) {
                    map.put(c2, new HashSet<>());
                }
    
                if(c1==c2) {
                    i++;
                    j++;
                } else { //c1 < c2
                    map.get(c2).add(c1);
                    break;
                }
                
            }
            
            while(i < s1.length()) {
                char c = s1.charAt(i);
                if(!map.containsKey(c)) {
                    map.put(c, new HashSet<>());
                }
                i++;
            }
            
            while(j < s2.length()) {
                char c = s2.charAt(j);
                if(!map.containsKey(c)) {
                    map.put(c, new HashSet<>());
                }
                j++;
            }
        }
        private void topological(Map<Character, Set<Character>> map, StringBuilder sb) {
            Queue<Character> qu = new LinkedList<>();
            for(Map.Entry<Character, Set<Character>> entry : map.entrySet()) {
                if(entry.getValue().size() == 0) {
                    qu.offer(entry.getKey());
                }
            }
            
            while(!qu.isEmpty()) {
                char a = qu.poll();
                sb.append(a);
                for(Map.Entry<Character, Set<Character>> entry : map.entrySet()) {
                    if(entry.getValue().contains(a)) {
                        entry.getValue().remove(a);
                        if(entry.getValue().size() == 0) {
                            qu.offer(entry.getKey());
                        }
                    }
                }
            }
            
            if(sb.length() != map.size()) {
                sb.setLength(0);
            }
        }
    }

Log in to reply
 

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