LeetCode

Appearance

567. Permutation in String ​

题目 ​

Given two strings s1 and 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 the substring of s2.

 

Example 1:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

 

Constraints:

  • 1 <= s1.length, s2.length <= 104
  • s1 and s2 consist of lowercase English letters.
Related Topics
  • 哈希表
  • 双指针
  • 字符串
  • 滑动窗口

  • 👍 1055
  • 👎 0

    • 思路 ​

    解法 ​

    py
    from collections import defaultdict

# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        window = defaultdict(int)
        needs = {}
        for i in s1:
            needs[i] = needs.get(i, 0) + 1

        left = right = 0
        len_s1 = len(s1)

        while right < len(s2):
            char = s2[right]
            window[char] += 1
            right += 1

            # shrink the window
            if right - left > len_s1:
                char_remove = s2[left]
                left += 1
                window[char_remove] -= 1
                if window[char_remove] == 0:
                    del window[char_remove]

            if window == needs:
                return True

        return False


# leetcode submit region end(Prohibit modification and deletion)
Solution().checkInclusion('adc', 'dcda')

    复杂度分析 ​

    • 时间复杂度O(N)
      • N = len(s1) + len(s2)
    • 空间复杂度O(1)
      • 创建 hashmap 的最大长度为 26 * 2 为一个常量，可计算空间复杂度为O(1)