dede模板 展柜网站源码,专业网站建设好发信息网,企业oa系统是什么,wordpress 主题viewpoint125.验证回文串 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后#xff0c;短语正着读和反着读都一样。则可以认为该短语是一个回文串 。 字母和数字都属于字母数字字符。 给你一个字符串 s#xff0c;如果它是回文串 #xff0c;返回 true #xff…125.验证回文串 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后短语正着读和反着读都一样。则可以认为该短语是一个回文串 。 字母和数字都属于字母数字字符。 给你一个字符串 s如果它是回文串 返回 true 否则返回 false 。
法1: re.sub
re.sub() 是 Python re正则表达式模块中的一个函数用于替换字符串中匹配指定正则表达式的部分基本语法: re.sub(pattern, repl, string, count0, flags0), 其中 pattern要匹配的正则表达式字符串或 re 对象repl替换的内容可以是字符串、函数或 lambda 表达式string要操作的原始字符串count可选最大替换次数默认为 0表示替换所有匹配项flags可选正则标志如 re.IGNORECASE 忽略大小写
class Solution(object):def isPalindrome(self, s)::type s: str:rtype: bools 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: bools 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)
