Leetcode 567. Permutation in String

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

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

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:

    1. def checkInclusion(self, s1: str, s2: str) -> bool:
    2.     n = len(s1)
    3.     stat = collections.Counter(s1)
    4.     stat['length'] = n
    5.     subs = collections.defaultdict(int)
    6.     for index, ch in enumerate(s2):
    7.         if ch in stat:
    8.             subs[ch] += 1
    9.             subs['length'] += 1
    10.         else:
    11.             subs = collections.defaultdict(int)
    12.             continue
    13.         if subs['length'] == stat['length']:
    14.             if stat == subs:
    15.                 return True
    16.             subs[s2[index - n + 1]] -= 1
    17.             subs['length'] -= 1
    18.     return False

Reference

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

发表评论

表情：
评论列表 （有 0 条评论，115人围观）

还没有评论，来说两句吧...

相关阅读