125.验证回文串 🟩

题目

LeetCode 简单

题目

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是回文串，返回 true ；否则，返回 false 。

示例：
输入: s = “A man, a plan, a canal: Panama”
输出：true
解释：“amanaplanacanalpanama” 是回文串。

输入：s = “race a car”
输出：false
解释：“raceacar” 不是回文串。

输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 “” 。
由于空字符串正着反着读都一样，所以是回文串。

题解

方法：正则 + 双指针

复杂度

时间复杂度：O(N)

s.toLowerCase()：遍历整个字符串将其转换为小写，时间复杂度为 O(N)
.match(/[a-z0-9]+/g)：正则匹配引擎会扫描整个字符串以找出匹配的子串，时间复杂度为 O(N)
s.join(‘’)：将匹配到的数组拼接成一个新的字符串，由于总字符数不会超过 N，时间复杂度为 O(N)
for 循环：双指针从两端向中间靠拢，最多执行 N/2 次，时间复杂度为 O(N)
空间复杂度：O(N)

s.toLowerCase() 会在内存中新建一个字符串，占用 O(N) 的空间（因为 JavaScript 中的字符串是不可变的）
.match() 会生成一个包含多个子串的数组，占用额外的 O(N) 空间
.join(‘’) 又会生成一个全新的字符串，再次占用 O(N) 的空间

function isPalindrome(s) {
    s = s.toLowerCase().match(/[a-z0-9]+/g)
    s = s ? s.join('') : ''
    for (let i = 0, j = s.length - 1; i < j; i++ , j--) {
        if (s[i] !== s[j]) {
            return false
        }
    }
    return true
}

const s = "A man, a plan, a canal: Panama"
console.log('🌰', isPalindrome(s))

执行结果

🌰 true

方法：双指针

复杂度

时间复杂度：O(N)
时间复杂度：O(1)

function isPalindrome(s) {
  let i = 0
  let j = s.length - 1

  // 辅助函数：判断字符是否是字母或数字
  const isValid = c => {
    return (
      (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')
    )
  }

  while (i < j) {
    // 左指针跳过非法字符
    while (i < j && !isValid(s[i])) {
      i++
    }
    // 右指针跳过非法字符
    while (i < j && !isValid(s[j])) {
      j--
    }

    // 比较，注意统一转换为小写再比较
    if (s[i].toLowerCase() !== s[j].toLowerCase()) {
      return false
    }
    i++
    j--
  }

  return true
}

const s = 'race a car'
console.log('🌰', isPalindrome(s))

执行结果

🌰 false

本页目录