字符串算法题

1.验证回文串【L125】

1. 双指针

思路：用正则去掉无关字符，然后对撞指针判断左右两边是否是相同的字符

复杂度：时间复杂度 O(n)，空间复杂度 O(1)

var isPalindrome = function(s) {
  var a = s.toLocaleLowerCase().match(/[a-z0-9]+/g);
  if (!a) return true;
  var slong = a.join("");
  var left = 0;
  right = slong.length - 1;
  while (left < right) {
    if (slong[left] == slong[right]) {
      left++;
      right--;
    } else {
      return false;
    }
  }
  return true;
};

2.最长回文子串【L5】

1. 双指针

解题思路：如果是回文子串，那么它的左右两边的元素肯定是对称的，我们可以使用左右指针，从当前元素向两边扩散，以找到最长字串。

时间复杂度：O(n^2)

空间复杂度 O(1)

var longestPalindrome = function(s) {
  let res = "";
  for (let i = 0; i < s.length; i++) {
    // 寻找长度为奇数的回文子串(以当前元素向两边扩散)
    const s1 = palindrome(s, i, i);
    // 寻找长度为偶数的回文子串(以s[i],s[i + 1])向两边扩散
    const s2 = palindrome(s, i, i + 1);
    res = res.length > s1.length ? res : s1;
    res = res.length > s2.length ? res : s2;
  }
  return res;
};
function palindrome(s, l, r) {
  // 左右指针，从s[l]和s[r]向两边扩散，找到最长回文串
  while (l >= 0 && r < s.length && s[l] == s[r]) {
    l--;
    r++;
  }
  return s.substr(l + 1, r - l - 1);
}

2. 动态规划

时间复杂度: O(n^2)

空间复杂度: O(n)

function longestPalindrome(s: string): string {
  const n = s.length;
  let [left, right] = [0, 1];
  let pre: number[] = [];
  let cur: number[] = [0, 1];
  for (let i = 0; i < n; i++) {
    for (const j of pre) {
      if (s[i] === s[j - 1]) {
        cur.push(j - 1);
        if (i - j + 2 > right - left) [left, right] = [j - 1, i + 1];
      }
    }
    [cur, pre] = [[i + 1, i + 2], cur];
  }

  return s.slice(left, right);
}

参考：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/5zui-chang-hui-wen-zi-chuan-cong-di-gui-44xrh/ (opens new window)

3.无重复字符的最长子串【L3 O48】

1. 滑动窗口 + set

时间复杂度：O(N)

空间复杂度：O(n)，即 set 的空间，最差的情况是 O(n)

var lengthOfLongestSubstring = function(s) {
  const set = new Set(); //判断滑动窗口内是否有重复元素
  let i = 0, //滑动窗口右边界
    j = 0, //滑动窗口左边界
    maxLength = 0;
  if (s.length === 0) {
    //极端情况
    return 0;
  }
  for (i; i < s.length; i++) {
    if (!set.has(s[i])) {
      //当前元素不在set中 就加入set 然后更新最大长度，i++继续下一轮循环
      set.add(s[i]);
      maxLength = Math.max(maxLength, set.size);
    } else {
      //set中有重复元素不断让j++ 并删除窗口之外的元素 直到滑动窗口内没有重复的元素
      while (set.has(s[i])) {
        set.delete(s[j]);
        j++;
      }
      set.add(s[i]); //放心将s[i]加入set中
    }
  }
  return maxLength;
};

2. 滑动窗口

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  var str = [],
    maxLength = 0;
  for (let i = 0; i < s.length; i++) {
    let index = str.indexOf(s[i]);
    if (index != -1) {
      str.splice(0, index + 1);
    }
    str.push(s[i]);
    maxLength = Math.max(maxLength, str.length);
  }
  return maxLength;
};

4.最小覆盖子串【L76】

1. 滑动窗口

解题思路：

（1）我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。

（2）我们先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求（包含了 t 中的所有字符）

（3）我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果

（4）重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头

思路的本质：增加窗口右边界，寻找一个可行解，在找到可行解的情况下增加窗口左边界，优化可行解，找到最优解

var minWindow = function(s, t) {
  // 需要的
  let need = {};
  // 窗口中的字符
  let window = {};
  for (let a of t) {
    // 统计需要的字符
    need[a] = (need[a] || 0) + 1;
  }
  // 左右指针
  let left = 0,
    right = 0;
  let valid = 0;
  // 最小覆盖子串的起始索引及长度
  let start = 0,
    len = Number.MAX_VALUE;
  while (right < s.length) {
    // 即将移入窗口的字符
    let c = s[right];
    // 右移窗口
    right++;
    if (need[c]) {
      // 当前字符在需要的字符中，则更新当前窗口统计
      window[c] = (window[c] || 0) + 1;
      if (window[c] == need[c]) {
        // 当前窗口和需要的字符匹配时，验证数量增加1
        valid++;
      }
    }
    // 当验证数量与需要的字符个数一致时，就应该收缩窗口了
    while (valid == Object.keys(need).length) {
      // 更新最小覆盖子串
      if (right - left < len) {
        start = left;
        len = right - left;
      }
      //即将移出窗口的字符
      let d = s[left];
      // 左移窗口
      left++;
      if (need[d]) {
        if (window[d] == need[d]) {
          valid--;
        }
        window[d]--;
      }
    }
  }
  return len == Number.MAX_VALUE ? "" : s.substr(start, len);
};

5.回文子串【L647】

6.反转字符串【L344】

7.反转字符串中的单词 III(L557)

1. 双指针

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
  let arr = s.split("");

  let l = 0,
    r = l;
  while (l < arr.length) {
    //找到结尾的空格
    while (arr[r] && arr[r] !== " ") {
      r++;
    }

    //反转单词
    for (let i = l, j = r - 1; i < j; i++, j--) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }

    //跳到下一个单词
    l = r + 1;
    r = l;
  }

  return arr.join("");
};

2. 数组 api

var reverseWords = function(s) {
  let arr = s
    .split("")
    .reverse()
    .join("");
  return arr
    .split(" ")
    .reverse()
    .join(" ");
};

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
  function reverse(str) {
    //功能函数，反转字符串。
    let newStr = "";
    for (let i of str) {
      newStr = i + newStr;
    }
    return newStr;
  }
  let sArr = s.split(" ");
  sArr = sArr.map((i) => reverse(i)); //反转每个字符串保存在sArr中;
  return sArr.join(" ");
};

8.字符串解码【L394】

10. 每一个字符及其出现的次数

function getMaxLengthStr(str) {
  let obj = {}; //定义一个新对象
  //循环遍历字符串
  for (let i = 0; i < str.length; i++) {
    // charAt()方法，返回某个指定位置的字符
    let char = str.charAt(i);
    // char就是对象obj的一个属性，obj[char]是属性值，obj[char]控制出现的次数(char是键值对中的键，obj[char]是值)
    if (obj[char]) {
      obj[char]++; //次数加1
    } else {
      obj[char] = 1; //若第一次出现，次数记为1
    }
  }
  // 输出的是完整的对象，记录着每一个字符及其出现的次数
  console.log(obj);

  // 遍历对象，找到出现次数最多的字符的次数
  let max = 0;
  // let maxChar = "";
  for (let key in obj) {
    if (max < obj[key]) {
      max = obj[key]; // max始终储存次数最多的那个
      // maxChar = key; //那么对应的字符就是当前的key
    }
  }
  // console.log("最多的字符是" + maxChar);
  // console.log("出现的次数是" + max);

  // 遍历对象，找到出现次数最多的字符和其次数
  for (let key in obj) {
    if (obj[key] == max) {
      //对应最多的字符就是当前的key
      //console.log(key);
      console.log("最多的字符是" + key);
      console.log("出现的次数是" + max);
    }
  }
}