add 269

fishercoder1534 · fishercoder1534 · commit 2e254941171b · 2017-06-23T06:44:29.000+09:00
diff --git a/README.md b/README.md
@@ -298,6 +298,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |272|[Closest Binary Search Tree Value II](https://leetcode.com/problems/closest-binary-search-tree-value-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/ClosestBinarySearchTreeValueII.java)| O(h+k)|O(h) | Hard| Stack
 |271|[Encode and Decode Strings](https://leetcode.com/problems/encode-and-decode-strings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/EncodeandDecodeStrings.java)| O(n)|O(1) | Medium| 
 |270|[Closest Binary Search Tree Value](https://leetcode.com/problems/closest-binary-search-tree-value/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_270.java)| O(h)|O(1) | Easy| DFS
+|269|[Alien Dictionary](https://leetcode.com/problems/alien-dictionary/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_269.java)| O(?)|O(?) | Hard| Topological Sort
 |268|[Missing Number](https://leetcode.com/problems/missing-number/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_268.java)| O(n)|O(1) | Easy| Bit Manipulation
 |267|[Palindrome Permutation II](https://leetcode.com/problems/palindrome-permutation-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/PalindromePermutationII.java)| O(n*n!)|O(n) | Medium|
 |266|[Palindrome Permutation](https://leetcode.com/problems/palindrome-permutation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/PalindromePermutation.java)| O(n)|O(1) | Easy|
diff --git a/src/main/java/com/fishercoder/solutions/AlienDictionary.java b/src/main/java/com/fishercoder/solutions/AlienDictionary.java
diff --git a/src/main/java/com/fishercoder/solutions/_269.java b/src/main/java/com/fishercoder/solutions/_269.java
@@ -0,0 +1,86 @@
+package com.fishercoder.solutions;
+
+import java.util.*;
+
+/**
+ * There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
+
+ For example,
+ Given the following words in dictionary,
+
+ [
+ "wrt",
+ "wrf",
+ "er",
+ "ett",
+ "rftt"
+ ]
+ The correct order is: "wertf".
+
+ Note:
+ You may assume all letters are in lowercase.
+ If the order is invalid, return an empty string.
+ There may be multiple valid order of letters, return any one of them is fine.
+ */
+public class _269 {
+
+    /**reference: https://discuss.leetcode.com/topic/28308/java-ac-solution-using-bfs*/
+    public static String alienOrder(String[] words) {
+        Map<Character, Set<Character>> map = new HashMap();
+        Map<Character, Integer> degree = new HashMap<>();
+        String result = "";
+        if (words == null || words.length == 0) return result;
+        for (String s : words) {
+            for (char c : s.toCharArray()) {
+                degree.put(c, 0);//keeps overwriting it, the purpose is to create one entry
+                //for each letter in the degree map
+            }
+        }
+        for (int i = 0; i < words.length - 1; i++) {
+            String cur = words[i];
+            String next = words[i + 1];
+            int length = Math.min(cur.length(), next.length());
+            for (int j = 0; j < length; j++) {
+                char c1 = cur.charAt(j);
+                char c2 = next.charAt(j);
+                if (c1 != c2) {
+                    Set<Character> set = new HashSet<>();
+                    if (map.containsKey(c1)) {
+                        set = map.get(c1);
+                    }
+                    if (!set.contains(c2)) {
+                        set.add(c2);
+                        map.put(c1, set);
+                        degree.put(c2, degree.get(c2) + 1);
+                    }
+                    break;
+                }
+            }
+        }
+        Queue<Character> queue = new LinkedList<>();
+        for (char c : degree.keySet()) {
+            if (degree.get(c) == 0) queue.add(c);
+        }
+        while (!queue.isEmpty()) {
+            char c = queue.remove();
+            result += c;
+            if (map.containsKey(c)) {
+                for (char c2 : map.get(c)) {
+                    degree.put(c2, degree.get(c2) - 1);
+                    if (degree.get(c2) == 0) {
+                        queue.add(c2);
+                    }
+                }
+            }
+        }
+        if (result.length() != degree.size()) return "";
+        return result;
+    }
+
+    public static void main(String ... args){
+        System.out.println("Hello world.");
+        String[] words = new String[]{"wrt","wrf","er","ett","rftt"};
+        String order = alienOrder(words);
+        System.out.print(order);
+    }
+}
