FindAllAnagramsInAString438

fluency03 · fluency03 · commit 0a7d3424e646 · 2018-07-26T20:49:12.000+02:00
diff --git a/README.md b/README.md
@@ -44,11 +44,11 @@
 | [Graph](https://github.com/fluency03/leetcode-java/blob/master/src/graph) |
 
 
-# Total: 356
+# Total: 357
 
 | Easy |  Medium | Hard | - |
 |:----:|:-------:|:----:|:-:|
-|  93  |   198   |  61  | 4 |
+|  94  |   198   |  61  | 4 |
 
 
 | Question | Solution | Difficulty |
@@ -317,6 +317,7 @@
 | [423. Reconstruct Original Digits from English](https://leetcode.com/problems/reconstruct-original-digits-from-english/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/ReconstructOriginalDigitsFromEnglish423.java) | Medium |
 | [425. Word Squares](https://leetcode.com/problems/word-squares/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/WordSquares425.java) | Hard |
 | [433. Minimum Genetic Mutation](https://leetcode.com/problems/minimum-genetic-mutation/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/MinimumGeneticMutation433.java) | Medium |
+| [438. Find All Anagrams in a String](https://leetcode.com/problems/find-all-anagrams-in-a-string/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/FindAllAnagramsInAString438.java) | Easy |
 | [443. String Compression](https://leetcode.com/problems/string-compression/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/StringCompression443.java) | Easy |
 | [445. Add Two Numbers II](https://leetcode.com/problems/add-two-numbers-ii/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/AddTwoNumbersII445.java) | Medium |
 | [448. Find All Numbers Disappeared in an Array](https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/FindAllNumbersDisappearedInAnArray448.java) | Easy |
diff --git a/src/FindAllAnagramsInAString438.java b/src/FindAllAnagramsInAString438.java
@@ -0,0 +1,66 @@
+/**
+ * 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".
+ */
+
+public class FindAllAnagramsInAString438 {
+    public List<Integer> findAnagrams(String s, String p) {
+        int[] map = new int[26];
+        for (char c: p.toCharArray()) {
+            map[c - 'a']++;
+        }
+        
+        List<Integer> res = new ArrayList<>();
+        int lenS = s.length();
+        int count = p.length();
+        if (lenS < count) return res;
+        char[] chars = s.toCharArray();
+        int i = 0;
+        int j = 0;
+        while (j < lenS) {
+            char c = chars[j];
+            while (i <= j && map[c - 'a'] <= 0) {
+                map[chars[i] - 'a']++;
+                i++;
+                count++;
+            }
+            if (i >= lenS) break;
+            map[c - 'a']--;  
+            j++;
+            count--;
+            if (count == 0) {
+                res.add(i);
+                map[chars[i] - 'a']++;
+                count++;
+                i++;
+            }
+        }
+        
+        return res;
+    }
+
+}
