Create find-all-anagrams-in-a-string.py

kamyu104 · web-flow · commit d3a08bb0a712 · 2016-10-23T18:32:05.000+08:00
diff --git a/Python/find-all-anagrams-in-a-string.py b/Python/find-all-anagrams-in-a-string.py
@@ -0,0 +1,59 @@
+# Time:  O(n)
+# Space: O(1)
+
+# 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".
+
+class Solution(object):
+    def findAnagrams(self, s, p):
+        """
+        :type s: str
+        :type p: str
+        :rtype: List[int]
+        """
+        result = []
+
+        cnts = [0] * 26
+        for c in p:
+            cnts[ord(c) - ord('a')] += 1
+        
+        left, right = 0, 0
+        while right < len(s):
+            cnts[ord(s[right]) - ord('a')] -= 1
+            while left <= right and cnts[ord(s[right]) - ord('a')] < 0:
+                cnts[ord(s[left]) - ord('a')] += 1
+                left += 1
+            if right - left + 1 == len(p):
+                result.append(left)
+            right += 1
+
+        return result
