leetcode_双指针 125.验证回文串

125.验证回文串

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

• 字母和数字都属于字母数字字符。

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

法1: re.sub

• re.sub() 是 Python re（正则表达式）模块中的一个函数，用于替换字符串中匹配指定正则表达式的部分
• 基本语法: re.sub(pattern, repl, string, count=0, flags=0), 其中
  • pattern：要匹配的正则表达式（字符串或 re 对象）
  • repl：替换的内容（可以是字符串、函数或 lambda 表达式）
  • string：要操作的原始字符串
  • count（可选）：最大替换次数（默认为 0，表示替换所有匹配项）
  • flags（可选）：正则标志（如 re.IGNORECASE 忽略大小写）

class Solution(object):def isPalindrome(self, s):""":type s: str:rtype: bool"""s = s.lower()  # 转换为小写s = re.sub(r'[^a-z0-9]', '', s)  # 移除非字母数字字符i = 0j = len(s) - 1while i < j:if s[i] == s[j]:i +=1j -=1else:return Falsereturn True

• 时间复杂度分析
  s.lower() ——O(n)
  re.sub() ——O(n)
  while 循环 ——O(n/2) = O(n)
  总时间复杂度：O(n)
• 空间复杂度：O(n)（因 re.sub() 生成了一个新字符串）

法2: 利用isalnum()

• isalnum() 可用于筛选字母数字字符，在处理字符串时经常用到，例如：

  • 验证用户名或密码格式
  • 清理文本数据
  • 检查输入是否包含非法字符

class Solution(object):def isPalindrome(self, s):""":type s: str:rtype: bool"""s = s.lower()  # 转换为小写s = ''.join(c for c in s if c.isalnum())  # 仅保留字母数字字符return s == s[::-1]  # 反转字符串后对比

• 时间复杂度分析
  s.lower() ——O(n)
  join() ——O(n)
  isalnum() ——O(n)
  s[::-1] —— O(n)
  总时间复杂度：O(n)
• 空间复杂度分析
  s.lower()：返回一个新的字符串，O(n) 空间
  ‘’.join(c for c in s if c.isalnum())：创建一个新的字符串存储过滤后的字符，O(n) 空间
  s[::-1]：创建一个字符串的反转副本，O(n) 空间
  总空间复杂度：O(n)