做哪种网站能赚到钱,深圳app定制开发多少钱,做花藤字网站,wordpress 主题 minty567. 字符串的排列 长度不变
给你两个字符串 s1 和 s2 #xff0c;写一个函数来判断 s2 是否包含 s1 ****的排列。如果是#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。
换句话说#xff0c;s1 的排列之一是 s2 的 子串
思路#xff1a;s1长度固定的窗…567. 字符串的排列 长度不变
给你两个字符串 s1 和 s2 写一个函数来判断 s2 是否包含 s1 ****的排列。如果是返回 true 否则返回 false 。
换句话说s1 的排列之一是 s2 的 子串
思路s1长度固定的窗口里的hash表和s2 要一致
用一个s1Map 保存 s1出现的字符和个数。遍历 s2维护窗口里的map
/*** param {string} s1* param {string} s2* return {boolean}*/
var checkInclusion function (s1, s2) {let map new Map();for (let i 0; i s1.length; i) {map.set(s1[i], map.get(s1[i]) 1 || 1);}let left 0;let s1Map new Map();for (let i 0; i s2.length; i) {// 扩大窗口维护窗口里字符出现的个数s1Map.set(s2[i], s1Map.get(s2[i]) 1 || 1);// 如果窗口满足条件if (i - left 1 s1.length) {// 满足要求的 更新答案if (isSameMap(s1Map, map)) {return true;}// 缩小窗口维护窗口减少的字符串s1Map.set(s2[left], s1Map.get(s2[left]) - 1);if (s1Map.get(s2[left]) 0) {s1Map.delete(s2[left]);}left;}}return false;
};function isSameMap(map1, map2) {if (map1.size ! map2.size) {return false;}for (let key of map1.keys()) {if (map1.get(key) ! map2.get(key)) {return false;}}return true;
}438 找到字符串中所有字母异位词 长度固定。
上一道题是是否有这道题是如果有找出所有答案。
/*** param {string} s* param {string} p* return {number[]}*/
var findAnagrams function(s, p) {let map new Map();for(let i 0; i p.length; i){map.set(p[i], map.get(p[i]) 1 || 1);}let left 0;let sMap new Map();let res [];for(let i 0; i s.length; i){// 扩大窗口维护窗口里字符出现的个数sMap.set(s[i], sMap.get(s[i]) 1 || 1);// 如果到达了限定长度if(i-left1 p.length){// 判断是否能够更新答案if(isSameMap(sMap, map)){res.push(left);}// 缩小窗口。sMap.set(s[left], sMap.get(s[left]) - 1);if(sMap.get(s[left]) 0){sMap.delete(s[left]);}left}}return res;
};// 比较两个map是否相同
function isSameMap(map1, map2) {if (map1.size ! map2.size) {return false;}for (let key of map1.keys()) {if (map1.get(key) ! map2.get(key)) {return false;}}return true;
}比较两个map是否相同。
可以使用map也可以使用一个26位数组都是小写或者都是大写然后再比较两个数组是否相同。
方法二使用频数数组。
var findAnagrams function (s, p) {let pArr new Array(26).fill(0);for (let i 0; i p.length; i) {pArr[p.charCodeAt(i) - a.charCodeAt(0)];}let sArr new Array(26).fill(0);let res [];let left 0;for (let i 0; i s.length; i) {sArr[s[i].charCodeAt(0) - a.charCodeAt(0)];if (i - left 1 p.length) {if (sArr.toString() pArr.toString()) {res.push(left);}sArr[s[left].charCodeAt(0) - a.charCodeAt(0)]--;left;}}return res;
};
