Shulou(Shulou.com)06/02 Report--

In this article, the editor introduces in detail "how to achieve palindrome detection in Python double-ended queue". The content is detailed, the steps are clear, and the details are handled properly. I hope this article "how to achieve palindrome detection in Python double-ended queue" can help you solve your doubts.

1. Double-ended queue

Double-ended queue Deque is an ordered data set, similar to a queue, its two ends can be called "head" and "tail", but data items in Deque can be added either from the head of the queue or from the end of the queue; data items can also be removed from both ends. In a sense, double-ended queues integrate stack and queue capabilities.

However, double-ended queues do not have inherent LIFO or FIFO characteristics. If double-ended queues are used to simulate stacks or queues, it is necessary for users to maintain the consistency of operations.

The operations to implement the abstract data type Deque,Deque definition with Python are as follows:

Deque (): create an empty double-ended queue

Add_front (item): add item to the team leader

Add_tail (item): add item to the end of the queue

Remove_front (): removes the data item from the head of the queue and returns the removed data item

Remove_tail (): removes the data item from the end of the queue and returns the removed data item

Is_empty (): returns whether Deque is empty

Get_size (): returns the number of data items contained in the Deque.

Define a double-end queue, and the code implementation is as follows:

Class Deque: def _ _ init__ (self): # create an empty double-ended queue self.items = [] def is_empty (self): # determine whether the double-ended queue is empty return self.items = = [] def add_front (self, item): # add the element self.items.append (item) def add_tail (self) from the head of the queue Item): # add the element self.items.insert (0) from the end of the queue Item) def remove_front (self): # remove element if self.is_empty (): raise Exception ('Queue is empty') return self.items.pop () def remove_tail (self): # Delete element if self.is_empty (): raise Exception (' Queue is empty') return from the end of the queue Self.items.pop (0) def get_size (self): # get the number of double-ended queue elements return len (self.items)

Operation complexity: add_front / remove_front,O (1); add_tail / remove_tail,O (n).

Second, palindromes detection

"palindromes" refer to words that are the same in both positive and negative pronunciation, such as radar, bob and toot; in Chinese: "Shanghai tap water comes from the sea" and "Shandong peanut flowers fall in Dongshan".

It is easy to solve the problem of "palindromes" with double-ended queues. First, add the words you need to determine from the end of the line to Deque, and then remove characters from both ends to determine whether they are the same, until there are 0 or 1 characters left in the Deque.

The algorithm is implemented as follows:

Def palindrome_check (string): # palindrome detection 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 () # team tail removal right = str_deque.remove_tail () # team head shift Except for if left! = right: # as long as once is not equal to palindromes check_flag = False # judge once check_flag is True is palindromes return check_flagprint (palindrome_check ("radar")) print (palindrome_check ("abcbac")) print (palindrome_check ("Shanghai tap water comes from the sea"))

Supplement

Python can also use double cursors to determine whether a string is a palindrome string.

Specify two cursor low,high from both ends of the string s

If the low cursor points to non-letters and numbers (that is, spaces and symbols), the low cursor moves back one bit

If the high cursor points to non-letters and numbers (that is, spaces and symbols), the high cursor moves forward one bit

Until both low and high point to numbers or letters, compare whether they are the same.

If the result of the comparison is True, the low moves back one bit and the high moves forward one bit

If the result of the comparison is False, it returns False directly.

Repeat the above judgment until low and high coincide, which means that you have completed the comparative judgment of the elements before and after the string s, and return True.

The code is as follows

Class Solution (object): def isPalindrome (self, s): "": type s: str: rtype: bool "" low = 0 high = len (s)-1 # returns True if len (s) if the string is empty or has only one character

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.