一、LeetCode——125.驗(yàn)證回文串
1.問(wèn)題描述
給定一個(gè)字符串，驗(yàn)證它是否是回文串，只考慮字母和數(shù)字字符，可以忽略字母的大小寫(xiě)。
說(shuō)明：本題中，我們將空字符串定義為有效的回文串。
2.示例
示例 1:
輸入: “A man, a plan, a canal: Panama”
輸出: True
示例 1:
輸入: “race a car”
輸出: False
示例 3:
輸入: “!!!”
輸出: True
二、解題分析
在排除空格及特殊字符的前提下，且不考慮字母大小寫(xiě)，字符串前后元素一一相同.
在字符串為空或只有一個(gè)字符時(shí)，應(yīng)該返回True
字符串的元素全部是符號(hào)是應(yīng)該返回True
三、解題思路及代碼實(shí)現(xiàn)
方法一：字符串切片
創(chuàng)建一個(gè)空字符串s_new，通過(guò)遍歷字符串s，將字符串s中的字母和數(shù)字，拼接到s_new中，
通過(guò)比較s_new[::-1] 和s_new得出結(jié)論?！咀址疄橛行虻臄?shù)據(jù)結(jié)構(gòu)，可以對(duì)其進(jìn)行切片操作】
代碼如下：
class Solution(object):
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
# 創(chuàng)建一個(gè)空字符串
s_new = ''
# 遍歷字符串s
for i in s:
# 判斷，如果是字母或數(shù)字，將其轉(zhuǎn)為小寫(xiě)拼接到字符串中
if i.isalnum():
s_new += i.lower()
# 切片后s_new[::-1]與s_new比較，并將結(jié)果返回
return s_new[::-1] == s_new
方法二：雙游標(biāo)判斷
從字符串s兩端指定兩個(gè)游標(biāo)low，high
如果low游標(biāo)指向了 非字母和數(shù)字（即空格和符號(hào)）,那么low游標(biāo)往后移一位；
如果high游標(biāo)指向了 非字母和數(shù)字（即空格和符號(hào)）,那么high游標(biāo)往前移一位；
直至low和high都指向了數(shù)字或字母，此時(shí)進(jìn)行比較，是否相同。
如果比較的結(jié)果是True，則low往后移一位，high往前移一位
如果比較的結(jié)果是False，則直接返回False
重復(fù)上述判斷，直至low和high重合，此時(shí)表示完成了字符串s內(nèi)前后元素的一一對(duì)比判斷，返回True即可。
代碼如下：
class Solution(object):
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
low = 0
high = len(s) - 1
#在字符串為空或只有一個(gè)字符時(shí)，返回True
if len(s) = 1:
return True
# 設(shè)定low和high對(duì)比的條件
while low high:
# 如果不是字母或數(shù)字，low往后移一位【low high為必須條件，不然會(huì)造成索引越界】
while not s[low].isalnum() and low high:
low += 1
# 如果不是字母或數(shù)字，high往前移一位
while not s[high].isalnum() and low high:
high -= 1
# 判斷：如果相同，繼續(xù)下一次對(duì)比；如果不相同，直接返回False
if s[low].lower() == s[high].lower():
low += 1
high -= 1
else:
return False
# low和high重合，即退出循環(huán)，表示前后都是一一對(duì)應(yīng)的，返回True
return True
四、總結(jié)
以上就是今天的解題，此題目從字符串切片的解題方式來(lái)看，考察了我們對(duì)字符串常見(jiàn)功能的掌握情況，而雙游標(biāo)的角度來(lái)看，主要考察了我們對(duì)游標(biāo)這一工具的靈活運(yùn)用，相信大家在學(xué)習(xí)基礎(chǔ)算法——快速排序時(shí)，會(huì)再次遇到雙游標(biāo)，而快速排序可以說(shuō)是相當(dāng)于在本文核心代碼的基礎(chǔ)上再嵌套一層外層循環(huán)。
補(bǔ)充：其他方法
1：首先將字符串大寫(xiě)字母轉(zhuǎn)為小寫(xiě)字母，然后去掉字符串中非字母和數(shù)字的其它字符，翻轉(zhuǎn)對(duì)比輸出結(jié)果（時(shí)間復(fù)雜度O(n)）
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
s = s.lower()
alphanumeric = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','0','1','2','3','4','5','6','7','8','9']
newStr = ""
for i in s:
if i in alphanumeric:
newStr += i
return newStr==newStr[::-1]
2：str.lower()+str.isalnum()（時(shí)間復(fù)雜度O(n)）
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
s = s.lower()
newStr = ""
for i in s:
if i.isalnum():
newStr += i
return newStr==newStr[::-1]
3：引入re模塊（正則表達(dá)式），re.sub()
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
s = s.lower()
import re
s = re.sub('[^a-z0-9]', "", s)
return s==s[::-1]
到此這篇關(guān)于Python實(shí)現(xiàn)"驗(yàn)證回文串"的幾種方法的文章就介紹到這了,更多相關(guān)Python 驗(yàn)證回文串內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
