125.驗證回文串

• 如果在將所有大寫字符轉(zhuǎn)換為小寫字符、并移除所有非字母數(shù)字字符之后，短語正著讀和反著讀都一樣。則可以認(rèn)為該短語是一個回文串 。

• 字母和數(shù)字都屬于字母數(shù)字字符。

• 給你一個字符串 s，如果它是回文串 ，返回 true ；否則，返回 false 。

法1: re.sub

• re.sub() 是 Python re（正則表達(dá)式）模塊中的一個函數(shù)，用于替換字符串中匹配指定正則表達(dá)式的部分
• 基本語法: re.sub(pattern, repl, string, count=0, flags=0), 其中
  • pattern：要匹配的正則表達(dá)式（字符串或 re 對象）
  • repl：替換的內(nèi)容（可以是字符串、函數(shù)或 lambda 表達(dá)式）
  • string：要操作的原始字符串
  • count（可選）：最大替換次數(shù)（默認(rèn)為 0，表示替換所有匹配項）
  • flags（可選）：正則標(biāo)志（如 re.IGNORECASE 忽略大小寫）

class Solution(object):def isPalindrome(self, s):""":type s: str:rtype: bool"""s = s.lower()  # 轉(zhuǎn)換為小寫s = re.sub(r'[^a-z0-9]', '', s)  # 移除非字母數(shù)字字符i = 0j = len(s) - 1while i < j:if s[i] == s[j]:i +=1j -=1else:return Falsereturn True

• 時間復(fù)雜度分析
  s.lower() ——O(n)
  re.sub() ——O(n)
  while 循環(huán) ——O(n/2) = O(n)
  總時間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(n)（因 re.sub() 生成了一個新字符串）

法2: 利用isalnum()

• isalnum() 可用于篩選字母數(shù)字字符，在處理字符串時經(jīng)常用到，例如：

  • 驗證用戶名或密碼格式
  • 清理文本數(shù)據(jù)
  • 檢查輸入是否包含非法字符

class Solution(object):def isPalindrome(self, s):""":type s: str:rtype: bool"""s = s.lower()  # 轉(zhuǎn)換為小寫s = ''.join(c for c in s if c.isalnum())  # 僅保留字母數(shù)字字符return s == s[::-1]  # 反轉(zhuǎn)字符串后對比

• 時間復(fù)雜度分析
  s.lower() ——O(n)
  join() ——O(n)
  isalnum() ——O(n)
  s[::-1] —— O(n)
  總時間復(fù)雜度：O(n)
• 空間復(fù)雜度分析
  s.lower()：返回一個新的字符串，O(n) 空間
  ‘’.join(c for c in s if c.isalnum())：創(chuàng)建一個新的字符串存儲過濾后的字符，O(n) 空間
  s[::-1]：創(chuàng)建一個字符串的反轉(zhuǎn)副本，O(n) 空間
  總空間復(fù)雜度：O(n)