Several Methods of Realizing 'Verifying Palindrome String' in Python

1. LeetCode--125. Verify palindrome string

1. Description of the problem

Given 1 string, verify that it is a palindrome string, considering only alphanumeric characters, and ignoring the case of letters.

Note: In this topic, we define an empty string as a valid palindrome string.

2. Examples

Example 1:
Input: "A man, a plan, a canal: Panama"
Output: True

Example 1:
Input: "race a car"
Output: False

Example 3:
Enter: "!!!"
Output: True

2. Problem solving analysis

Elements 11 are the same before and after the string, excluding spaces and special characters, and regardless of the case of letters.
True should be returned when the string is empty or only 1 character
String elements are all symbols should return True

3. Problem solving ideas and code implementation

Method 1: String slicing

Create an empty string s_new, and stitch the letters and numbers in the string s into s_new by traversing the string s,
A conclusion is drawn by comparing s_new [::-1] with s_new. "Strings are ordered data structures that can be sliced."
The code is as follows:

class Solution(object):
  def isPalindrome(self, s):
    """
    :type s: str
    :rtype: bool
    """
    #  Create 1 Empty string 
    s_new = ''
    #  Traversing string s
    for i in s:
     #  Judge, if it is a letter or number, convert it to lowercase and splice it into a string 
      if i.isalnum():
        s_new += i.lower()
    #  After slicing s_new[::-1] And s_new Compare and return the result 
    return s_new[::-1] == s_new

Method 2: Double cursor judgment

Specify two cursors 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 (i.e. spaces and symbols), the high cursor moves forward 1 bit;
Until low and high both point to numbers or letters, compare them to see if they are the same.
If the result of the comparison is True, low is moved one bit backward and high is moved one bit forward
If the result of the comparison is False, False is returned directly
Repeat the above judgment until low and high coincide, which means that 11 comparison judgments of the elements before and after the string s are completed, and then return to True.

The code is as follows:

class Solution(object):
  def isPalindrome(self, s):
    """
    :type s: str
    :rtype: bool
    """
    low = 0
    high = len(s) - 1
    # When the string is empty or only 1 Characters, returns the True
    if len(s) <= 1:
      return True
    #  Setting low And high Contrast conditions 
    while low < high:
     #  If it's not letters or numbers, low Move backwards 1 Bit " low < high Is a necessary condition, otherwise the index will cross the boundary. " 
      while not s[low].isalnum() and low < high:
        low += 1
      #  If it's not letters or numbers, high Move forward 1 Bit 
      while not s[high].isalnum() and low < high:
        high -= 1
       #  Judgment: If it is the same, continue 1 Sub-contrast; If not, return directly False
      if s[low].lower() == s[high].lower():
        low += 1
        high -= 1
      else:
        return False
    # low And high Overlap, that is, exit the loop, means that both before and after are 11 Corresponding, returning True
   return True

4. Summary

That's today's problem solving. According to the solution of string slicing, Examined our mastery of the common functions of strings, From the perspective of double cursors, we mainly examine our flexible use of cursors. I believe that when we learn the basic algorithm-quick sorting, we will encounter double cursors again, and quick sorting can be said to be equivalent to nesting one layer of outer loops on the basis of the core code of this paper.

Supplement: Other methods

1: First, convert the upper case letters of the string to lower case letters, then remove other characters of the string that are not letters and numbers, and flip and compare the output results (time complexity 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 () (Time Complexity 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: Introducing re module (regular expression), 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]