双指针

lc125. 验证回文串简单

题目描述

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明： 本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串

示例 2:

输入: "race a car"
输出: false
解释："raceacar" 不是回文串

思路

正则去掉除了英文以外其他字符，然后双指针前后开始匹配

var isPalindrome = function(s) {
  s = s.replace(/[^\w]|_/g, '').toLowerCase()
  let left = 0, right = s.length - 1
  while(left <= right) {
    if(s[left] === s[right]) {
      left++
      right--
    } else {
      return false
    }
  }
  return true
};

lc344. 反转字符串简单

题目描述

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须 原地 (opens new window)修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

var reverseString = function(s) {
  let left = 0, right = s.length - 1
  while(left <= right) {
    [s[left], s[right]] = [s[right], s[left]]
    left++
    right--
  }
};

lc647. 回文子串中等hot

题目描述

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

中心扩展

回文串有两种中心形式：

• 以一个字符为中心（奇数长度）
• 以两个字符之间为中心（偶数长度）

我们从每个字符/字符对出发向两边扩展，统计回文。

var countSubstrings = function(s) {
    let count = 0;

    const expand = (left, right) => {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            count++;
            left--;
            right++;
        }
    };

    for (let i = 0; i < s.length; i++) {
        expand(i, i);     // 奇数长度中心
        expand(i, i + 1); // 偶数长度中心
    }

    return count;
};

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

空间复杂度:O(1)