add solution of problem 428: find all anagrams in a string

ppulse · ppulse · commit aeed40d5f01c · 2016-10-30T23:54:24.000+08:00
diff --git a/FindAllAnagramsInAString438/README.md b/FindAllAnagramsInAString438/README.md
@@ -0,0 +1,40 @@
+Given a string **s** and a **non-empty** string **p**, find all the start indices of **p**'s anagrams in **s**.
+
+Strings consists of lowercase English letters only and the length of both strings **s** and **p** will not be larger than 20,100.
+
+The order of output does not matter.
+
+#####Example 1:
+```
+
+######Input:
+s: "cbaebabacd" p: "abc"
+
+######Output:
+[0, 6]
+
+######Explanation:
+The substring with start index = 0 is "cba", which is an anagram of "abc".
+The substring with start index = 6 is "bac", which is an anagram of "abc".
+
+```
+#####Example 2:
+```
+
+######Input:
+s: "abab" p: "ab"
+
+######Output:
+[0, 1, 2]
+
+######Explanation:
+The substring with start index = 0 is "ab", which is an anagram of "ab".
+The substring with start index = 1 is "ba", which is an anagram of "ab".
+The substring with start index = 2 is "ab", which is an anagram of "ab".
+
+```
+
+####思路
+只包含小写字母，因此可用26个char的数组作为哈希表，O(1)查找
+然后用KMP来移动指针
+
diff --git a/FindAllAnagramsInAString438/Solution.java b/FindAllAnagramsInAString438/Solution.java
@@ -0,0 +1,61 @@
+public class Solution {
+    public List<Integer> findAnagrams(String s, String p) {
+        List<Integer> result = new ArrayList<Integer>();  
+        Set<Character> charSet = new HashSet<Character>();
+        
+        for (int i = 0; i < p.length(); i++)
+            charSet.add(p.charAt(i));
+        
+        int i = 0;
+        while (i < s.length()) {
+            int[] map = getMap(p);
+            boolean matched = false;
+            int cnt = 0;
+            int j = i;
+            
+            for (; j < s.length(); j++) {
+                if (map[s.charAt(j) - 'a'] > 0) {
+                    map[s.charAt(j) - 'a']--;
+                    cnt++;
+                
+                    if (cnt == p.length()) {
+                        result.add(i);
+                        matched = true;
+                        break;
+                    }
+                } else if (cnt < p.length()) {
+                    break;
+                } 
+            }
+            
+            if (matched) {
+                i++;
+            } else if (j < s.length() && charSet.contains(s.charAt(j))) {
+            	i++;
+            } else { 
+            	if (i == j) {
+                    if (charSet.contains(s.charAt(j)))
+                        i = j;
+                    else
+                        i = j + 1;
+                }
+                else {
+                    i = j;
+                }
+            }
+            
+        }
+        
+        return result;
+    }
+    
+    private int[] getMap(String p) {
+        int[] map = new int[26];
+        
+        for (int i = 0; i < p.length(); i++) {
+            map[p.charAt(i) - 'a']++;
+        }
+        
+        return map;
+    }
+}
