字符串
双指针
用两个指针来定位一个子数组，其中一个指针指向数组的第1个数字，另一个指针指向数组的最初一个数字，那么两个指针之间所蕴含的就是一个子数组。
能够在挪动这两个指针的同时，统计两个指针之间的字符串中字符呈现的次数，这样能够解决很多常见的面试题，如在一个字符串中定位另一个字符串的变位词等。
因为这种类型的面试题都与统计字母呈现的次数无关，咱们常常应用哈希表来存储每个元素呈现的次数，因而解决这种类型的面试题通常须要同时应用双指针和哈希表。
- 字符串中的变位词
题目：输出字符串s1和s2，如何判断字符串s2中是否蕴含字符串s1的某个变位词？如果字符串s2中蕴含字符串s1的某个变位词，则字符串s1至多有一个变位词是字符串s2的子字符串。假如两个字符串中只蕴含英文小写字母。例如，字符串s1为"ac"，字符串s2为"dgcaf"，因为字符串s2中蕴含字符串s1的变位词"ca"，因而输入为true。如果字符串s1为"ab"，字符串s2为"dgcaf"，则输入为false。
由变位词的定义可知，变位词具备以下几个特点。首先，一组变位词的长度肯定雷同；其次，组成变位词的字母汇合肯定雷同，并且每个字母呈现的次数也雷同。
/** * @param {string} s1 * @param {string} s2 * @return {boolean} */var checkInclusion = function(s1, s2) { if(s2.length < s1.length) { return false; } var areAllZero = function(counts) { for(let i of counts) { if(i !== 0) { return false } } return true; } const counts = new Array(26).fill(0) for(let i = 0; i < s1.length; i++) { counts[s1.charCodeAt(i) - 97]++; counts[s2.charCodeAt(i) - 97]--; } if(areAllZero(counts)) { return true; } for (let i = s1.length; i < s2.length; ++i) { counts[s2.charCodeAt(i) - 97]-- counts[s2.charCodeAt(i - s1.length) - 97]++ if(areAllZero(counts)) { return true } } return false;};- 字符串中的所有变位词
题目：输出字符串s1和s2，如何找出字符串s2的所有变位词在字符串s1中的起始下标？假如两个字符串中只蕴含英文小写字母。例如，字符串s1为"cbadabacg"，字符串s2为"abc"，字符串s2的两个变位词"cba"和"bac"是字符串s1中的子字符串，输入它们在字符串s1中的起始下标0和5。
/** * @param {string} s * @param {string} p * @return {number[]} */var findAnagrams = function(s1, s2) { if(s2.length > s1.length) { return []; } let result = []; const counts = new Array(26).fill(0); var areAllZero = function(counts) { for(let i of counts) { if(i !== 0) { return false } } return true; } for(let i = 0; i < s2.length; i++){ counts[s2.charCodeAt(i)-97]++ counts[s1.charCodeAt(i)-97]-- } if(areAllZero(counts)) { result.push(0) } for(let i = s2.length; i < s1.length; i++) { counts[s1.charCodeAt(i)-97]-- counts[s1.charCodeAt(i-s2.length)-97]++ if(areAllZero(counts)) { result.push(i-s2.length+1) } } return result;};- 不含反复字符的最长子字符串
题目：输出一个字符串，求该字符串中不含反复字符的最长子字符串的长度。例如，输出字符串"babcca"，其最长的不含反复字符的子字符串是"abc"，长度为3。
/** * @param {string} s * @return {number} */var lengthOfLongestSubstring = function(s) { if(s.length == 0) return 0 if(s.length == 1) return 1 const map = new Map(); let max = 0 // 双指针 let left = 0 let right = 0 var areAllZero = function(counts) { for(let i of counts) { if(i[1] === 2) { return false } } return true; } while(right < s.length) { if(map.get(s.charAt(right)) !== 1) { map.set(s.charAt(right), (map.get(s.charAt(right)) || 0) + 1) right++ if(map.get(s.charAt(right)) === 1) { max = Math.max(right - left, max) } } else { map.set(s.charAt(left), (map.get(s.charAt(left)) || 0) - 1) left++ } } max = Math.max(right - left, max) return max;};- 蕴含所有字符的最短字符串
输出两个字符串s和t，请找出字符串s中蕴含字符串t的所有字符的最短子字符串。例如，输出的字符串s为"ADDBANCAD"，字符串t为"ABC"，则字符串s中蕴含字符'A'、'B'和'C'的最短子字符串是"BANC"。如果不存在符合条件的子字符串，则返回空字符串""。如果存在多个符合条件的子字符串，则返回任意一个。
var minWindow = (s, t) => { const charToCount = new Map(); for(let ch of t) { charToCount.set(ch, (charToCount.get(ch) || 0) + 1) } let count = charToCount.size; let start = 0, end = 0, minStart = 0, minEnd = 0; let minLength = Infinity; while(end < s.length || (count == 0) && end == s.length) { if(count > 0) { let endCh = s.charAt(end); if(charToCount.get(endCh)!== undefined) { charToCount.set(endCh, charToCount.get(endCh)-1) if (charToCount.get(endCh) === 0) { count-- } } } else { if (end - start < minLength) { minLength = end - start minStart = start minEnd = end } let startCh = s.charAt(start); if(charToCount.get(startCh)!==undefined) { charToCount.set(startCh, charToCount.get(startCh) + 1) if(charToCount.get(startCh) == 1) { count++ } } start++ } } return minLength < Infinity ? s.substring(minStrat, minEnd) : "";}上述代码中只有一个while循环，用来把两个变量从0减少到字符串s的长度。如果字符串的长度是n，那么工夫复杂度就是O（n）。能够应用一个哈希表来统计每个字符呈现的次数。哈希表的键为字符，假如字符串中只有英文字母，那么哈希表的大小不会超过256，辅助空间的大小不会随着字符串长度的减少而减少，因而空间复杂度是O（1）。
回文字符串
- 无效的回文
给定一个字符串 s ，验证 s 是否是 回文串 ，只思考字母和数字字符，能够疏忽字母的大小写。
/** * @param {string} s * @return {boolean} */var isPalindrome = function(s) { let l = 0; let r = s.length - 1; const reg = /[a-zA-Z0-9]/ while(l <= r) { if(!reg.test(s.charAt(l))) { l++ continue } if(!reg.test(s.charAt(r))) { r-- continue } if(s.charAt(r).toLocaleLowerCase() !== s.charAt(l).toLocaleLowerCase()) { return false } else { l++ r-- } } return true};- 最多删除一个字符失去回文
给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符是否失去一个回文字符串。
/** * @param {string} s * @return {boolean} */var validPalindrome = function (s) { let low = 0, high = s.length - 1; const valid = (low, high) => { for (let i = low, j = high; i < j; i++, j--) { if (s[i] != s[j]) return false; } return true; }; while (low < high) { if (s[low] == s[high]) { low++; high--; } else { return valid(low + 1, high) || valid(low, high - 1); } } return true;};我没有思考到2种状况都让他执行
- 回文子字符串的个数
题目：给定一个字符串，请问该字符串中有多少个回文间断子字符串？例如，字符串"abc"有3个回文子字符串，别离为"a"、"b"和"c"；而字符串"aaa"有6个回文子字符串，别离为"a"、"a"、"a"、"aa"、"aa"和"aaa"。
后面都是从字符串的两端开始向里挪动指针来判断字符串是否是一个回文,其实也能够换一个方向从字符串的核心开始向两端延长。如果存在一个长度为m的回文子字符串，则别离再向该回文的两端延长一个字符，并判断回文前后的字符是否雷同。如果雷同，就找到了一个长度为m+2的回文子字符串。
/** * @param {string} s * @return {number} */var countSubstrings = function(s) { if(s == null || s.length == 0) { return 0 } let count = 0; for(let i = 0; i < s.length; i++) { count += countPalindrome(s, i, i) count += countPalindrome(s, i, i + 1) } return count};var countPalindrome = function(s, start, end) { let count = 0; while(start >= 0 && end < s.length && s.charAt(start) == s.charAt(end)) { count++ start-- end++ } return count;}上述解法依然须要两个嵌套的循环，因而工夫复杂度是O（n2）。该解法只用到了若干变量，其空间复杂度是O（1）。
总结