Leetcode 567. Permutation in String

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

解析：Version 1，此题与leetcode 438非常类似，思路是一样的。判断s2是否包含s1的变换，可以采用字典的方法，即每个字母的个数及类型相等。先统计字符串s1的字母个数并记录其长度在stat中，遍历字符串s2，如果字母在stat中，则将其记录到字典subs中，否则重置subs，当subs['length'] = stat['length']时，比较二者是否相等，如果相等，直接返回True，否则，字符串继续遍历，为保证subs长度与stat长度一致，此时，subs中移除s2[index - n + 1]字符，同时长度减1。

• Version 1

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        n = len(s1)
        stat = collections.Counter(s1)
        stat['length'] = n
        subs = collections.defaultdict(int)
        for index, ch in enumerate(s2):
            if ch in stat:
                subs[ch] += 1
                subs['length'] += 1
            else:
                subs = collections.defaultdict(int)
                continue
            if subs['length'] == stat['length']:
                if stat == subs:
                    return True
                subs[s2[index - n + 1]] -= 1
                subs['length'] -= 1
        return False

Reference

1. https://leetcode.com/problems/permutation-in-string/