leetcode

commit 6b43fe61b0a788d116e4cb53aabc1be621f97263
parent 92867d838ca087431ddacbe3c438460922b8a871
Author: Jack Sangdahl <jack@pngu.org>
Date:   Fri,  4 Oct 2024 21:05:13 -0600

567. permutation in string

Diffstat:
A
permutation_in_string.py
 | 
40
++++++++++++++++++++++++++++++++++++++++

1 file changed, 40 insertions(+), 0 deletions(-)
diff --git a/permutation_in_string.py b/permutation_in_string.py
@@ -0,0 +1,40 @@
+# 567. Permutation in String
+from collections import Counter
+
+"""
+given two strings 's1 s2' return true if 's2' contains a permutation of 's1'
+or false otherwise. in other words, return true if one of 's1's permutations
+is in the substring of 's2'
+"""
+
+
+class Solution(object):
+    def checkInclusion(self, s1, s2):
+        """
+        :type s1: str
+        :type s2: str
+        :rtype: bool
+        """
+        cnt, n, match = Counter(s1), len(s1), 0
+        for i in range(len(s2)):
+            if s2[i] in cnt:
+                if not cnt[s2[i]]:
+                    match -= 1
+                cnt[s2[i]] -= 1
+                if not cnt[s2[i]]:
+                    match += 1
+            if i >= n and s2[i - n] in cnt:
+                if not cnt[s2[i - n]]:
+                    match -= 1
+                cnt[s2[i - n]] += 1
+                if not cnt[s2[i - n]]:
+                    match += 1
+            if match == len(cnt):
+                return True
+        return False
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.checkInclusion(s1="ab", s2="eidbaooo"))
+    print(obj.checkInclusion(s1="ab", s2="eidboaoo"))