双指针

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 = ''
  for(let i = 0; i < s.length; i++) {
    let s1 = '', s2 = ''
    for(let j = i; j < s.length; j++) {
      s1 = s1 + s[j]
      s2 = s[j] + s2
      if(s1 === s2) count++
    }
  }
  return count
};

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

空间复杂度:O(n)

思路二：中心扩展

枚举所有可能的回文中心 s[i] 或 s[i]、s[i + 1]

若回文子串长度为奇数则其中心为 s[i]

回文子串长度为偶数则其中心为 s[i]、s[i + 1]；

以中心向左右两边扩展，即左边界 l 减一右边界 r 加1，如果 s[l] 与 s[r] 相等则回文数加1

var countSubstrings = function(s) {
  let count = 0;
    for (let i = 0; i < s.length; i++) {
        for (let l = i, r = i; l >= 0 && s[l] === s[r]; l--, r++) count++;
        for (let l = i, r = i + 1; l >= 0 && s[l] === s[r]; l--, r++) count++;
    }
    return count;
};

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

空间复杂度:O(1)

思路三：还是中心扩展 易懂

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
  let count = s.length
  let len = s.length
  for(let i = 0; i < len; i++){
    for(let j = i + 1; j < len; j++){
      let temp = s.substr(i, j - i + 1)
      if(isSub(temp)){
        count++
      }
    }
  }
  return count
};
const isSub = str => {
  let a = 0
  let b = str.length - 1
  while(a <= b){
    if(str[a] !== str[b]){
      return false
    }
    a++
    b--
  }
  return true
}

• 时间复杂度为O(n^2)，需要两层遍历。
• 空间复杂度为O(1)