字符串的排列
LeetCode.567，难度中等
题目
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba"). 复制代码
示例2:
输入: s1= "ab" s2 = "eidboaoo" 输出: False 复制代码
注意：
- 输入的字符串只包含小写字母
- 两个字符串的长度都在 [1, 10,000] 之间
解法
理解一下题意，要求s1的字符串排列之一是第二个字符串的子串，比如ab是eidbaooo的子串，ba也是eidbaooo的子串，同样的baoo也是eidbaooo的子串，所以这个规则可以抽象一下，如果eidbaooo里面存在一个子串，该子串的字符和s1的字符相同，且该子串字符出现的次数和s1中的字符出现次数相同，因此，可以考虑滑动窗口的思路。
首先维护一个map1来保存s1的字符以及每个字符出现的次数，再维护一个map2来保存当前窗口中的每个字符以及每个字符出现的次数，如果map1和map2相同，则说明滑动窗口中的字符子串和s1的排列之一相同，否则继续往右滑动。
- 初始化，以s1长度为准，来构造两个map，map1 = { a: 1, b: 1 }，map2 = { e: 1, i: 1 }。此时滑动窗口中的字符串是'ei'
- 从s2的第3个（前两个已经被初始化过）字符'd'开始遍历，map1和map2不同。此时窗口字符串是'ei'，删掉左边的'e'，更新map2= { i: 1 }；加入第3个字符'd'，更新map2 = { i: 1, d: 1 }
- 此时遍历到第4个字符'b'，map1和map2不同。此时窗口字符串是'id'，删掉左边的'i'，更新map2={ d: 1 }；加入第4个字符串'b'，更新map2={ d: 1, b: 1 }
- 此时遍历到第5个字符'a'，map1和map2不同。此时窗口的字符串是'db'，删掉左边的'd'，更新map2={ b: 1 }；加入第5个字符串'a'，更新map2={ b: 1, a: 1 }
- 此时遍历到滴6个字符'o'，map1和map2相同，返回true
代码如下：
/** * @param {string} s1 * @param {string} s2 * @return {boolean} */ let checkMapEqual = function(m1, m2) { let keys1 = Object.keys(m1), keys2 = Object.keys(m2); if(keys1.length !== keys2.length) return false; for(let i = 0;i < keys1.length;i++) { const curKey = keys1[i]; if(m1[curKey] !== m2[curKey]) return false; } return true; } let checkInclusion = function(s1, s2) { if(s1.length > s2.length) return false; let map1 = {}, map2 = {}; const len1 = s1.length, len2 = s2.length; // 初始化map for(let i = 0;i < len1;i++) { if(map1[s1[i]]) { map1[s1[i]]++ } else { map1[s1[i]] = 1; } if(map2[s2[i]]) { map2[s2[i]]++ } else { map2[s2[i]] = 1; } } for(let i = len1;i < len2;i++) { if(checkMapEqual(map1, map2)) { return true; } // 将窗口最左边的字符删去 const leftChar = s2[i-len1]; if(map2[leftChar] === 1) { delete map2[leftChar]; } else { map2[leftChar]--; } // 在窗口右边加入一个字符 const rightChar = s2[i]; if(map2[rightChar]) { map2[rightChar]++; } else { map2[rightChar] = 1; } } return checkMapEqual(map1, map2); }; 复制代码
字符串相乘
LeetCode.43，难度中等
题目
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
示例 1:
输入: num1 = "2", num2 = "3" 输出: "6"复制代码
示例 2:
输入: num1 = "123", num2 = "456" 输出: "56088"复制代码
说明：
num1和num2的长度小于110。num1和num2只包含数字0-9。num1和num2均不以零开头，除非是数字 0 本身。- 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
解法
先分析一下题目字符串相乘，要想模拟两个数字相乘，需要解决逐位相乘、再逐个相加的问题，过程中需要注意正确进位，比如'123'和'456'相乘：
- 3和456相乘，得到1368；
- 2和456相乘，得到912，因为2是十位，所以得到9120；
- 1和456相乘，得到456，因为1是百位，所以得到45600；
- 把3次乘积相加，加的过程中也要注意逐位相加，别忘了进位
代码如下：
/** * @param {string} num1 * @param {string} num2 * @return {string} */ const multiplyStep = (num1, pos, num2) => { let res = ''; let carry = 0; for(let i = num2.length-1;i >= 0;i--) { const cur = num2[i]; let product = parseInt(cur)*num1; if(carry) { product += carry; carry = 0; } if(product >= 10) { carry = parseInt(product/10); product = product%10 } res = product + res; } if(carry) { res = carry + res; } while(pos) { res += 0; pos--; } return res; } const addStep = (num1, num2) => { let len1 = num1.length; let len2 = num2.length; let num1Reversed = num1.split('').reverse().join(''); let num2Reversed = num2.split('').reverse().join(''); let index = 0; let res = ''; let carry = false; while(index < len1 && index < len2) { const char1 = num1Reversed[index]; const char2 = num2Reversed[index]; let sum = parseInt(char1) + parseInt(char2); if(carry) { sum += 1; carry = false; } if(sum >= 10) { carry = true; sum = sum%10; } res += sum; index++; } while(index < len1) { let cur = num1Reversed[index]; if(carry) { carry = false cur = parseInt(cur)+1; } if(cur >= 10) { cur = cur%10; carry = true; } res += cur; index++; } while(index < len2) { let cur = num2Reversed[index]; if(carry) { carry = false cur = parseInt(cur)+1; } if(cur >= 10) { cur = cur%10; carry = true; } res += cur; index++; } if(carry) { res += 1; carry = false; } return res.split('').reverse().join(''); } var multiply = function(num1, num2) { if(num1 === '0' || num2 === '0') return '0'; let strArr = []; let res = '0'; for(let i = num1.length-1;i >= 0;i--) { strArr.push( multiplyStep(num1[i], num1.length-1-i, num2) ) } console.log(strArr); for(let i = 0;i < strArr.length;i++) { res = addStep(res, strArr[i]); } return res; };
