6ms JAVA solution


  • 0
    D
    public class Solution {
        public String alienOrder(String[] words) {
            if (words.length==0) return "";
            int[] counts = new int[26];
            Letter[] letters = new Letter[26];
            HashSet<Integer> set = new HashSet<Integer>(36);
            int prevLength = words[0].length();
            for (int i=0; i<prevLength;i++) set.add(words[0].charAt(i)-'a');
            for (int i=1; i<words.length; i++) {
                int curLength = words[i].length(), j=0;
                while (j<prevLength) {
                    if (j==curLength) return "";
                    int x = words[i-1].charAt(j)-'a';
                    int y = words[i].charAt(j)-'a';
                    set.add(y);
                    if (x!=y) {
                        Letter letter = letters[x];
                        if (letter==null) {
                            letter = new Letter();
                            letters[x]=letter;
                        }
                        letter.following.add(y);
                        counts[y]++;
                        break;
                    }
                    j++;
                }
                while (j<curLength) set.add(words[i].charAt(j++)-'a');
                prevLength = curLength;
            }
            Queue<Integer> queue = new LinkedList<Integer>();
            StringBuilder sb = new StringBuilder();
            for (int i=0;i<26; i++) if (counts[i]==0 && set.contains(i)) queue.offer(i);
            while(!queue.isEmpty()) {
                int i = queue.poll();
                sb.append((char)('a'+i));
                Letter letter = letters[i];
                if (letter!=null) {
                    for (int j: letter.following) {
                        counts[j]--;
                        if (counts[j]==0) queue.offer(j);
                    }
                }
            }
            return sb.length()==set.size()?sb.toString():"";
        }
        private class Letter{
            public List<Integer> following; 
            public Letter(){
                following = new ArrayList<Integer>(25);
            }
        }
    }
    

Log in to reply
 

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