class Deque:
? ? def __init__(self): ? # 創(chuàng)建空的雙端隊(duì)列
? ? ? ? self.items = []

? ? def is_empty(self): ? # 判斷雙端隊(duì)列是否為空
? ? ? ? return self.items == []

? ? def add_front(self, item): ? # 從隊(duì)首加入元素?
? ? ? ? self.items.append(item)

? ? def add_tail(self, item): ? ?# 從隊(duì)尾加入元素?
? ? ? ? self.items.insert(0, item)

? ? def remove_front(self): ? ? ?# 從隊(duì)首刪除元素?
? ? ? ? if self.is_empty():
? ? ? ? ? ? raise Exception('Queue is empty')
? ? ? ? return self.items.pop()

? ? def remove_tail(self): ? ? ? # 從隊(duì)尾刪除元素?
? ? ? ? if self.is_empty():
? ? ? ? ? ? raise Exception('Queue is empty')
? ? ? ? return self.items.pop(0)

? ? def get_size(self): ? ? ? ? ?# 獲取雙端隊(duì)列元素?cái)?shù)量
? ? ? ? return len(self.items)

def palindrome_check(string): ? # 回文檢測(cè)
? ? str_deque = Deque()
? ? for item in string:
? ? ? ? str_deque.add_front(item)
? ? ? ??
? ? check_flag = True
? ? while str_deque.get_size() > 1 and check_flag:
? ? ? ? left = str_deque.remove_front() ? # 隊(duì)尾移除
? ? ? ? right = str_deque.remove_tail() ? # 隊(duì)首移除
? ? ? ? if left != right: ? # 只要有一次不相等 ? 不是回文
? ? ? ? ? ? check_flag = False
? ? # 判斷完一遍 ? check_flag為T(mén)rue ?是回文
? ? return check_flag

print(palindrome_check("radar"))
print(palindrome_check("abcbac"))
print(palindrome_check("上海自來(lái)水來(lái)自海上"))

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