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)