字符串专题
1.驼峰转换（正则）
驼峰命名camelCase和短横线命名kebab-case
（1）将'getElementById'转换成'get-element-by-id'
const getKebabCase = function(str) { // str.replace不会改变原字符串，因此需要直接return return str.replace(/[A-Z]/g, (i) => '-' + i.toLowerCase()); } 复制代码（2）将'get-element-by-id'转换成'getElementById'
const getCamelCase = function(str) { // /w匹配任意的字母、数字和下划线 // $0,$1匹配成功的第n组内容 return str.replace(/-(\w)/g, ($0, $1) => $1.toUpperCase()); } 复制代码2.无重复字符的最长子串（3）
滑动窗口 O(n)：
使用两个指针lt，rt表示滑动窗口的左右边界，使用map结构来存放滑动窗口中的字符串，key代表该字符，value代表该字符的索引。
每当向右移动右指针时，都会先判断map结构是否包含该字符，是就更新左指针，不论是否包含都需要更新map、更新res。
const longestSubString = function(str) { let lt = rt = res = 0; const map = new Map(); for(; rt < str.length; rt++) { if (map.has(str[rt])) { // 滑动窗口有重复字符，右移lt lt = Math.max(lt, map.get(str[rt]) + 1); // 必须用max，为了保持lt不倒退 } map.set(str[rt], rt); // key是字符，value是字符的索引，方便lt的变化 res = Math.max(res, rt - lt + 1); } return res; } 复制代码3.比较版本号（165）
spilt + parseInt O（m + n）：
const compareVersion = function(version1, version2) { const v1 = version1.split('.'), v2 = version2.split('.'); // 遍历的长度取两个版本号的最长长度 for (let i = 0; i < v1.length || i < v2.length; i++) { let num1 = i < v1.length ? parseInt(v1[i]) : 0, num2 = i < v2.length ? parseInt(v2[i]) : 0; if (num1 > num2) return 1; if (num1 < num2) return -1; } return 0; } 复制代码4.字符串相加（415）
常规思路O(max(m, n))：模拟竖式加法，定义两个指针p1和p2分别指向两个数字的末尾，定义变量add维护当前进位，另外，对于位数较短的数字进行了补0操作。
优化：对补0操作优化，比如一个长度很长和一个长度很短的字符做加法，可以只对后面几位做加法。
const addStrings = function(s1, s2) { let p1 = s1.length - 1, p2 = s2.length - 1; // p指针初始指向个位 let add = 0, res = []; // 进位 while (p1 >= 0 || p2 >= 0 || add) { //@ 进位add不为0 // 因为字符串不支持直接修改，只能取出字符进行赋值操作 let ch1 = s1[p1] ? s1[p1] : '0', ch2 = s2[p2] ? s2[p2] : '0'; let sum = parseInt(ch1) + parseInt(ch2) + add; add = parseInt(sum / 10); res.push(sum % 10); p1 -= 1; p2 -= 1; } return res.reverse().join(''); //@ reverse } 复制代码5.有效的括号（20）
栈O(n)：
遍历字符串s，当遇到左括号时会入栈，遇到右括号时、如果此时栈为空或者字符不等于栈顶元素，那就肯定不是有效括号，如果等于栈顶符号就出栈。最后通过判断栈大小返回布尔值。
const isValid = function(s) { if (s.length % 2 === 1) return false; // 长度为奇数长，无效括号 const map = new Map([ [')', '('], ['}', '{'], [']', '['], ]); const stack = []; for (let ch of s) { // 比for循环更高效 if (map.has(ch)) { // 右括号 // 如果stack为空，或者不等于栈顶元素 if (!stack.length || stack[stack.length - 1] !== map.get(ch)) { return false; } stack.pop(); } else { // 左括号 stack.push(ch); } } return !stack.length; //@ 同时包含两种情况，或者两个if代替 } 复制代码6.最长回文子串（5）
中心扩散法 O(n^2)：
空间复杂度O(1)
const longetSubString = function(s) { if (s.length < 2) return s; let res = ''; // 遍历字符串，提取每个字符的回文串 function sliceString(left, right) { while (left >= 0 && right < s.length && s[left] === s[right]) { left -= 1; // 同步扩大范围 right += 1; } // 跳出循环，此时left和right并不满足，left + 1和right - 1才满足 let len = (right - 1) - (left + 1) + 1; res = len > res.length ? s.slice(left + 1, right) : res; // slice提取不包含right字符 } for (let i = 0; i < s.length; i++) { // 假设回文串是奇数个 sliceString(i, i); // 假设回文串是偶数个 if (i + 1 < s.length) { sliceString(i, i + 1); } } return res; } 复制代码7.最长公共前缀（14）
初始化最长公共前缀s的值是第一个字符串，遍历后面的字符串、依次进行比较，最终结果即为最长公共前缀。如果查找过程中出现s为空的情况，则直接返回""。
时间复杂度 O(s)。
const longestCommonPrefix = function(strs) { if (strs.length === 1) return ""; let s = strs[0]; for (let i = 1; i < strs.length; i++) { let j = 0; for (; j < Math.min(s.length, strs[i].length); j++) { if (s[j] !== strs[i][j]) { // 字符不相等 break; } } // 如果放在第2层循环里面，由于j遍历的范围，当有一方长度为1时，会导致一次也进入不了if判断，直接返回s s = s.substr(0, j); //@ 位置放在第2层for循环中 if (!s) return s; } return s; } 复制代码8.括号生成（22）
DFS：
首先，一个合法的括号序列需要满足两个条件：（1）左右括号数量相等；（2）任意前缀中左括号数量 >= 右括号数量，这样就能保证每个右括号都能找到相匹配的左括号。
设计思想：将生成n对合法括号序列组合的问题，转化为序列的每一位要填什么的问题。 因为合法的括号序列，任意前缀中左括号数量一定大于等于右括号数量，所以（1）如果左括号数量不大于等于n时，我们就可以放一个左括号 （2）如果右括号数量小于左括号的数量，我们就可以放一个右括号。
搜索过程：function dfs (n, lc, rc, str)。 1.初始时左括号数量lc和右括号数量rc都为0。 2. 如果 lc小于括号对数n， 那在当前合法序列str后拼接左括号。3.如果右括号数量小于左括号数量，则在当前序列str后拼接右括号。 4.当lc和rc数量都等于n时，将当前合法序列str加入结果数组res中。
时间复杂度：经典卡特兰数问题，O(Cn-2n)，结合图理解。
const res = []; // 全局变量 function dfs(n, lc, rc, str) { if (lc == n && rc == n) { res.push(str); } else { //@ 注意结构，两个if都要走 if (lc < n) dfs(n, lc + 1, rc, str + "("); if (rc < n && lc > rc) dfs(n, lc, rc + 1, str +")"); } } const generateValidString = function(n) { dfs(n, 0, 0, ""); return res; }
作者：二阶导
链接：https://juejin.cn/post/7014112315020673060