【定长滑动窗口】28. 实现 strStr()、567. 字符串的排列、1456. 定长子串中元音的最大数目

28. 实现 strStr()

leetcode: 问题详情.

b站: 视频讲解.

解法一、定长滑动窗口

模板1

class Solution(object):def strStr(self, haystack, needle):""":type haystack: str:type needle: str:rtype: int"""# len(haystack) >= 0lh, ln = len(haystack), len(needle)if ln == 0:return 0for start in range(lh - ln + 1):if haystack[start: start+ln] == needle:return startreturn -1

模板2

class Solution(object):def strStr(self, haystack, needle):""":type haystack: str:type needle: str:rtype: int"""# len(haystack) >= 0lh, ln = len(haystack), len(needle)if ln == 0:return 0start = 0for end in range(ln-1, lh):  # range(0, 5) = [0, 1, 2, 3, 4]# print(haystack[start:end+1])if haystack[start:end+1] == needle:return startstart += 1return -1

567. 字符串的排列

leetcode: 问题详情.

b站: 视频讲解.

class Solution(object):def template(self, s: str): mapping = {
    }for i in s:if i not in mapping.keys():mapping[i] = 1else:mapping[i] += 1return mappingdef checkInclusion(self, s1: str, s2: str) -> bool:start = 0l1, l2 = len(s1), len(s2)# from collections import Counter 也可以调用Counter实现 = templatetemplate = self.template(s1)  # 用字典来解决无序的问题# print(template)for end in range(l1-1, l2):mapping = self.template(s2[start: end+1])# print(mapping)if template == mapping:return Truestart += 1return False

1456. 定长子串中元音的最大数目

leetcode: 问题详情.

class Solution(object): def isVowel(self, ch):return  int(ch in 'aeiou')def maxVowels(self, s, k):num = 0max_num = 0start = 0for i in range(k):  # 统计第一个窗口的元音字母个数num += self.isVowel(s[i])max_num = numfor end in range(k, len(s)):  # 窗口向后移动num = num + self.isVowel(s[end]) - self.isVowel(s[start]) # 当前窗口的元音个数max_num = max(max_num, num)start += 1return max_num