Leetcode 567. Permutation in String

た入场券 2022-09-09 00:13 114阅读 0赞

文章作者：Tyan  
博客：[noahsnail.com][] | [CSDN][] | [简书][Link 1]

## 1. Description ##

![Permutation in String][]

## 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/][https_leetcode.com_problems_permutation-in-string]

[noahsnail.com]: http://noahsnail.com
[CSDN]: http://blog.csdn.net/quincuntial
[Link 1]: http://www.jianshu.com/users/7731e83f3a4e/latest_articles
[Permutation in String]: /images/20220829/a0d607086d9e49879f694505f68aea0e.png
[https_leetcode.com_problems_permutation-in-string]: https://leetcode.com/problems/permutation-in-string/