利用双端队列解决回文词算法

什么是回文词：

指正读和倒读都是一样的词，

中文如：

上海自来水来自海上

山东落花生花落东山

英文如：

eve,eye,ewe(母羊),gig(马车),level,madam,minim(量滴)

什么是双端队列？

deque，全名double-ended queue）是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。

双端队列并不具有内在LIFO或者FIFO的特性，如果使用双端队列来模拟栈或者队列，需要使用者自行维护操作的一致性。

代码如下：

class?Deque():
????def?__init__(self):
????????self.items=[]

????#?判断双端队列是否为空
????def?isEmpty(self):
????????return?len(self.items)

????#?往队首中加值
????def?addTop(self,item):
????????self.items.append(item)

????#?往队尾中加值
????def?addLast(self,item):
????????self.items.insert(0,?item)


????#?从队首中移除值
????def?removeTop(self):
????????return?self.items.pop()


????#?从队尾中移除值
????def?removeLast(self):
????????return?self.items.pop(0)

????#?双端队列的大小
????def?size(self):
????????return?len(self.items)


def?palchecker(str):
????dobj=Deque()

????for?s?in?str:
????????dobj.addTop(s)

????mark=True
????while?dobj.size()>1?and?mark:
????????top_str=dobj.removeTop()
????????last_str=dobj.removeLast()

????????if?top_str!=last_str:
????????????mark=False

????return?mark

if?__name__?==?'__main__':
????print(palchecker('abababa'))
????print(palchecker('上海自来水来自海上'))
????print(palchecker('山东落花生花落东山'))
????print(palchecker('山东'))

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!