Python回文检测
叶庭云 人气:1一、双端队列
双端队列 Deque 是一种有次序的数据集,跟队列相似,其两端可以称作"首" 和 "尾"端,但 Deque 中数据项既可以从队首加入,也可以从队尾加入;数据项也可以从两端移除。某种意义上说,双端队列集成了栈和队列的能力。
但双端队列并不具有内在的 LIFO 或者 FIFO 特性,如果用双端队列来模拟栈或队列,需要由使用者自行维护操作的一致性。
用 Python 实现抽象数据类型Deque,Deque定义的操作如下:
- Deque():创建一个空双端队列;
- add_front(item):将 item 加入队首;
- add_tail(item):将 item 加入队尾;
- remove_front():从队首移除数据项,返回值为移除的数据项;
- remove_tail():从队尾移除数据项,返回值为移除的数据项;
- is_empty():返回 Deque 是否为空;
- get_size():返回 Deque 中包含数据项的个数。
定义双端队列,代码实现如下:
class Deque: def __init__(self): # 创建空的双端队列 self.items = [] def is_empty(self): # 判断双端队列是否为空 return self.items == [] def add_front(self, item): # 从队首加入元素 self.items.append(item) def add_tail(self, item): # 从队尾加入元素 self.items.insert(0, item) def remove_front(self): # 从队首删除元素 if self.is_empty(): raise Exception('Queue is empty') return self.items.pop() def remove_tail(self): # 从队尾删除元素 if self.is_empty(): raise Exception('Queue is empty') return self.items.pop(0) def get_size(self): # 获取双端队列元素数量 return len(self.items)
操作复杂度:add_front / remove_front,O(1);add_tail / remove_tail,O(n)。
二、回文检测
“回文词” 指正读和反读都一样的词,如radar、bob、toot;中文:“上海自来水来自海上”,“山东落花生花落东山”。
用双端队列很容易解决 “回文词” 问题,先将需要判定的词从队尾加入Deque,再从两端同时移除字符判定是否相同,直到 Deque 中剩下 0 个或 1 个字符。
算法实现如下:
def palindrome_check(string): # 回文检测 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() # 队尾移除 right = str_deque.remove_tail() # 队首移除 if left != right: # 只要有一次不相等 不是回文 check_flag = False # 判断完一遍 check_flag为True 是回文 return check_flag print(palindrome_check("radar")) print(palindrome_check("abcbac")) print(palindrome_check("上海自来水来自海上"))
补充
Python还可以通过双游标判断字符串是否是回文串
从字符串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
加载全部内容