diff options
author | Jack Sangdahl <[email protected]> | 2024-10-04 21:05:13 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-10-04 21:05:13 -0600 |
commit | 6b43fe61b0a788d116e4cb53aabc1be621f97263 (patch) | |
tree | 3f609c60ae54690623f09018ec2af59e0c375eac | |
parent | 92867d838ca087431ddacbe3c438460922b8a871 (diff) | |
download | leetcode-6b43fe61b0a788d116e4cb53aabc1be621f97263.tar.gz leetcode-6b43fe61b0a788d116e4cb53aabc1be621f97263.zip |
567. permutation in string
-rw-r--r-- | permutation_in_string.py | 40 |
1 files changed, 40 insertions, 0 deletions
diff --git a/permutation_in_string.py b/permutation_in_string.py new file mode 100644 index 0000000..7511b54 --- /dev/null +++ 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")) |