滑动窗口
给你两个字符串 s1 和 s2 ,写一个函数来判断 s2 是否包含 s1 的排列。如果是,返回 true ;否则,返回 false 。
换句话说,s1 的排列之一是 s2 的 子串 。
示例 1:
输入:s1 = “ab” s2 = “eidbaooo”
输出:true
解释:s2 包含 s1 的排列之一 (“ba”).
示例 2:
输入:s1= “ab” s2 = “eidboaoo”
输出:false
如果s2的某一子串是s1的排列,则返回true,否则返回false。首先要满足这个条件,s2的长度一定要大于等于s1的长度,即:
字符串中保存的是小写字母,可以用一个大小为26的数组来保存s1中字母出现的次数,因为满足条件的s2的子串长度一定等于s1的长度,所以在s2中维护一个长度为s1的长度的滑动窗口,同样用一个数组来表示该窗口中字母出现的次数:
因为s1是排列,所以只要窗口中的元素全部在s1中出现,则说明该窗口是s1的一个排列,这样我们就只需要比较每次滑动窗口后两个数组是否相同了,维护滑动窗口数组即每次去掉最左边元素的同时将最右边即将进入窗口元素加进来,通俗点讲就是把要出窗口的元素在数组中-1,要加进来的元素在数组中+1。
整体代码如下:
Original: https://www.cnblogs.com/liangren-na/p/16437580.html
Author: 良人呐
Title: 567.字符串中的排列
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/619845/
转载文章受原作者版权保护。转载请注明原作者出处!