字符串专题

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;
}