Python實現"驗證回文串"的幾種方法

Posted on by

一、LeetCode——125.驗證回文串

1.問題描述

給定一個字符串，驗證它是否是回文串，隻考慮字母和數字字符，可以忽略字母的大小寫。

說明：本題中，我們將空字符串定義為有效的回文串。

2.示例

示例 1:
輸入: “A man, a plan, a canal: Panama”
輸出: True

示例 1:
輸入: “race a car”
輸出: False

示例 3:
輸入: “!!!”
輸出: True

二、解題分析

在排除空格及特殊字符的前提下，且不考慮字母大小寫，字符串前後元素一一相同.
在字符串為空或隻有一個字符時，應該返回True
字符串的元素全部是符號是應該返回True

三、解題思路及代碼實現

方法一：字符串切片

創建一個空字符串s_new，通過遍歷字符串s，將字符串s中的字母和數字，拼接到s_new中，
通過比較s_new[::-1] 和s_new得出結論。【字符串為有序的數據結構，可以對其進行切片操作】
代碼如下：

class Solution(object):
  def isPalindrome(self, s):
    """
    :type s: str
    :rtype: bool
    """
    # 創建一個空字符串
    s_new = ''
    # 遍歷字符串s
    for i in s:
     # 判斷，如果是字母或數字，將其轉為小寫拼接到字符串中
      if i.isalnum():
        s_new += i.lower()
    # 切片後s_new[::-1]與s_new比較，並將結果返回
    return s_new[::-1] == s_new

方法二：雙遊標判斷

從字符串s兩端指定兩個遊標low，high
如果low遊標指向瞭 非字母和數字（即空格和符號）,那麼low遊標往後移一位；
如果high遊標指向瞭 非字母和數字（即空格和符號）,那麼high遊標往前移一位；
直至low和high都指向瞭數字或字母，此時進行比較，是否相同。
如果比較的結果是True，則low往後移一位，high往前移一位
如果比較的結果是False，則直接返回False
重復上述判斷，直至low和high重合，此時表示完成瞭字符串s內前後元素的一一對比判斷，返回True即可。

代碼如下：

class Solution(object):
  def isPalindrome(self, s):
    """
    :type s: str
    :rtype: bool
    """
    low = 0
    high = len(s) - 1
    #在字符串為空或隻有一個字符時，返回True
    if len(s) <= 1:
      return True
    # 設定low和high對比的條件
    while low < high:
     # 如果不是字母或數字，low往後移一位【low < high為必須條件，不然會造成索引越界】
      while not s[low].isalnum() and low < high:
        low += 1
      # 如果不是字母或數字，high往前移一位
      while not s[high].isalnum() and low < high:
        high -= 1
       # 判斷：如果相同，繼續下一次對比；如果不相同，直接返回False
      if s[low].lower() == s[high].lower():
        low += 1
        high -= 1
      else:
        return False
    # low和high重合，即退出循環，表示前後都是一一對應的，返回True
   return True

四、總結

以上就是今天的解題，此題目從字符串切片的解題方式來看，考察瞭我們對字符串常見功能的掌握情況，而雙遊標的角度來看，主要考察瞭我們對遊標這一工具的靈活運用，相信大傢在學習基礎算法——快速排序時，會再次遇到雙遊標，而快速排序可以說是相當於在本文核心代碼的基礎上再嵌套一層外層循環。

補充：其他方法

1：首先將字符串大寫字母轉為小寫字母，然後去掉字符串中非字母和數字的其它字符，翻轉對比輸出結果（時間復雜度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()（時間復雜度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模塊（正則表達式），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]

到此這篇關於Python實現”驗證回文串”的幾種方法的文章就介紹到這瞭,更多相關Python 驗證回文串內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：

    None Found