Leetcode - Alien Dictionary

My code:

public class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> adj = new HashMap<Character, Set<Character>>();
        Map<Character, Integer> degree = new HashMap<Character, Integer>();
        for (String word : words) {
            for (char c : word.toCharArray()) {
                degree.put(c, 0);
            }
        }
        
        String ret = "";
        if (words == null || words.length == 0) {
            return ret;
        }
        
        for (int i = 0; i < words.length - 1; i++) {
            String w1 = words[i];
            String w2 = words[i + 1];
            int len = Math.min(w1.length(), w2.length());
            for (int j = 0; j < len; j++) {
                char c1 = w1.charAt(j);
                char c2 = w2.charAt(j);
                if (c1 != c2) {
                    Set<Character> set = adj.get(c1);
                    if (set == null) {
                        set = new HashSet<Character>();
                    }
                    if (!set.contains(c2)) {
                        set.add(c2);
                        adj.put(c1, set);
                        degree.put(c2, degree.get(c2) + 1);
                    }
                    break;
                }
            }
        } 
        
        Queue<Character> q = new LinkedList<Character>();
        for (Character c : degree.keySet()) {
            if (degree.get(c) == 0) {
                q.offer(c);
            }
        }
        
        while (!q.isEmpty()) {
            char c = q.poll();
            ret += "" + c;
            if (adj.containsKey(c)) {
                for (Character nei : adj.get(c)) {
                    degree.put(nei, degree.get(nei) - 1);
                    if (degree.get(nei) == 0) {
                        q.offer(nei);
                    }
                }
            }
        }
        
        if (ret.length() != degree.keySet().size()) {
            return "";
        }
        else {
            return ret;
        }
    }
}

reference:
https://discuss.leetcode.com/topic/28308/java-ac-solution-using-bfs

根据论坛后面一个大神的说法。这道题目一共分为两个步骤。
第一，构图，同时，构造 degree
第二，topological sort

Anyway, Good luck, Richardo! -- 09/27/2016

本来基本做出来了。奈何 testcase 更新了，可能会输入一些不满足字典顺序的例子，我们要立即返回""

My code:

public class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> adj = new HashMap<Character, Set<Character>>();
        Map<Character, Integer> degree = new HashMap<Character, Integer>();
        for (String word : words) {
            for (char c : word.toCharArray()) {
                degree.put(c, 0);
            }
        }

        String ret = "";
        if (words == null || words.length == 0) {
            return ret;
        }
        
        for (int i = 0; i < words.length - 1; i++) {
            String w1 = words[i];
            String w2 = words[i + 1];
            int len = Math.min(w1.length(), w2.length());
            int j = 0;
            for (; j < len; j++) {
                char c1 = w1.charAt(j);
                char c2 = w2.charAt(j);
                if (c1 != c2) {
                    Set<Character> set = adj.get(c1);
                    if (set == null) {
                        set = new HashSet<Character>();
                    }
                    if (!set.contains(c2)) {
                        set.add(c2);
                        adj.put(c1, set);
                        degree.put(c2, degree.get(c2) + 1);
                    }
                    break;
                }
            }
            if (j >= len && w1.length() > w2.length()) {
                return "";
            }
        } 

        Queue<Character> q = new LinkedList<Character>();
        for (Character c : degree.keySet()) {
            if (degree.get(c) == 0) {
                q.offer(c);
            }
        }

        while (!q.isEmpty()) {
            char c = q.poll();
            ret += "" + c;
            if (adj.containsKey(c)) {
                for (Character nei : adj.get(c)) {
                    degree.put(nei, degree.get(nei) - 1);
                    if (degree.get(nei) == 0) {
                        q.offer(nei);
                    }
                }
            }
        }

        if (ret.length() != degree.keySet().size()) {
            return "";
        }
        else {
            return ret;
        }
    }
}

Anyway, Good luck, Richardo! -- 10/18/2016