2021-11-14剑指OfferII014.字符串中的变位词

2021-11-14剑指OfferII014.字符串中的变位词

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        n1 = len(s1)
        n2 = len(s2)
        if n1 > n2:
            return False
        d1 = dict()
        #创建一个字典,通过键值对来取出数据
        for i in s1:
            if i not in d1:
                d1[i] = 1
            else:
                d1[i] += 1
                #统计第一个字符串当中的字母出现的次数
        left = 0
        right = n1 - 1
        d2 = dict()
        #从第二个字符串当中截取和第一个字符串同样长度的字符,用哈希表统计一波每个字符所出现的次数
        for i in range(left,right+1,1):
            if s2[i] not in d2:
                d2[s2[i]] = 1
            else :
                d2[s2[i]] += 1    
        #range(start,stop,step)
        #确定范围,在【start,end)每隔step来确定步长
        if operator.eq(d1,d2):
            return True
        #如果两个字典一摸一样,就说明有相同的异位的字母,
        while right+1 <= n2-1:
            #窗口的移动,下一个窗口从s1的末尾开始移动
            if s2[right+1] not in d2:
                d2[s2[right+1]] = 1
            else :
                d2[s2[right+1]] += 1
                #窗口的大小保持不变,窗口向右边移动一格
                #窗口的左边缩小一格
            d2[s2[left]] -= 1
            if d2[s2[left]]==0:
                d2.pop(s2[left])
                #如果左边的格子没有用了,就抛弃掉
            if operator.eq(d1,d2):
                return True
            left = left + 1
            right = right + 1

        return False

1、先比较两个字符串的长度,如果要在第二个字符串里面寻找比它长的第一个字符串的子串,那肯定没戏。所以一开始要比较两个字符串的长度。

2、如果第一个字符串比第二个字符串短,说明第一个字符串可能是第二个字符串的子串,先将第一个字符串制作成hash_map
1)从第二个字符串的开始截取一段和第一个字符串同样长的子串制作成哈希表,如果这两个哈希表完全相同,说明第一个肯定是第二个字符串的子串。
2)之后滑动窗口不断向后挪动,注意新加入一个字符和减去一个字符的处理。
每次移动一次就比较两个哈希表是否相同,只要有一次相同,就满足第一个字符串是第二个字符串的子串。

上一篇:网络流


下一篇:[LeetCode]面试题 01.09. 字符串轮转