567. 字符串的排列(Medium)

题目描述

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

样例

Input: s1 = "ab" s2 = "eidbaooo"
Ontput: True
解释: s2 包含 s1 的排列之一 ("ba").

题解

本题同 字符串中所有字母异位词解题思路一致

Python代码示例

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        s1Arr = {}
        s2Arr = {}
        char = 'a'
        # 正常的初始化操作
        while char <= 'z':
          s1Arr[char] = 0
          s2Arr[char] = 0
          char = chr(ord(char) + 1)
				
        # 正常的初始化操作
        for char in s1:
            s1Arr[char] += 1

        l, r = 0, -1
        ans = []
        while r + 1 < len(s2):
            r += 1
            s2Arr[s2[r]] += 1

            while s2Arr[s2[r]] > s1Arr[s2[r]]: # 左移
                s2Arr[s2[l]] -= 1
                l += 1
            if r - l + 1 == len(s1):
                return True 
        return False

Go 代码示例

func checkInclusion(s1 string, s2 string) bool {
    stack1 := make(map[byte]int, 0)
    stack2 := make(map[byte]int, 0)
    char := byte('a')
    for char <= byte('z') {
        stack1[char] = 0
        stack2[char] = 0
        char ++
    }
    for i, s := range s1 { 
        stack1[byte(s)]++ // for 循环中遍历的 s 是 rune 类型的
        // 也可以写成
        // stack1[s[i]]++  // string 中存的是 byte， 即 s[i] 是 byte 类型的
        
    }

    l, r := 0, -1
    n := len(s2)
    for r + 1 < n {
        r++
        stack2[s2[r]]++
        for stack2[s2[r]] > stack1[s2[r]] {
            stack2[s2[l]]--
            l++
        }
        if r - l + 1 == len(s1) {
            return true
        }
    }
    return false 
}