给你两个字符串 s1 和 s2 ,写一个函数来判断 s2 是否包含 s1 的排列。如果是,返回 true ;否则,返回 false 。
换句话说,s1 的排列之一是 s2 的 子串 。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/permutation-in-string
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
双指针
示例 1:
输入:s1 = "ab" s2 = "eidbaooo"
输出:true
解释:s2 包含 s1 的排列之一 ("ba").
示例 2:
输入:s1= "ab" s2 = "eidboaoo"
输出:false
提示:
1 <= s1.length, s2.length <= 104
s1 和 s2 仅包含小写字母
思路
- 因为全是小写字母的字符串,可以根据对应的ASCLL码去比较是否相等或者计数
- 用数组去记录字母的数量,下标表示对应的字母 比如 a => 97 那么 【a-z】 - a呢 就是【97-123】- 97 就是 0-26
- 那可以用长度为26的数组去记录 s1 和 s2 中的目标字符串
- s2 的目标字符串我们可以用双指针去记录
/**
* @param {string} s1
* @param {string} s2
* @return {boolean}
*/
var checkInclusion = function (s1, s2) {
let arr1 = new Array(26).fill(0)
let arr2 = new Array(26).fill(0)
for (let i = 0; i < s1.length; i++) {
if (!s2[i]) return false
++arr1[s1[i].charCodeAt(0) - 'a'.charCodeAt(0)] // 对应的元素就是 对应的数量值
++arr2[s2[i].charCodeAt(0) - 'a'.charCodeAt(0)]
}
if (arr1.toString() === arr2.toString()) {
return true
}
let star = 0;
let end = star + s1.length - 1;
while (end < s2.length - 1) {
end++
if (s2[star] === s2[end]) { //优化(虽然没有看到实际的效率 占用内存还是和原来差不多),如果窗口移动 减去的左边值和右边增加的值一样那么跳过本次比较操作
star++
continue;
}
--arr2[s2[star].charCodeAt(0) - 'a'.charCodeAt(0)]
++arr2[s2[end].charCodeAt(0) - 'a'.charCodeAt(0)]
if (arr1.toString() === arr2.toString()) {
return true
}
star++
}
return false
};
温故而知新
- 字符串获取ascll码
string.charCodeAt(index)
[a-z] => [97-123]