Validates palindrome strings

Subject address: leetcode-cn.com/problems/va…

Given a string, verify that it is a palindrome string, considering only alphanumeric characters, regardless of letter case.

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

Example 1:

Input:"A man, a plan, a canal: Panama"Output:true
Copy the code

Example 2:

Input:"race a car"Output:false
Copy the code

Solution one: double pointer

First check whether the two strings are palindromic strings, that is, whether the original string and the reverse sequence are equal, that is not the previous written reverse string. I’m just swapping heads and tails, whether heads and tails are the same. But first we need to get the alphanumeric string from the original string and ignore case

public boolean isPalindrome(String s) {
    if(s == null || s.length() == 0) return true;
    char[] arr = s.toCharArray();
    int n = arr.length;
    StringBuilder cs = new StringBuilder();
    for (int i = 0; i < n; i++) {
        char c = arr[i];
        if (check(c)) {
            cs.append(change(c));
        }
    }
    n = cs.length();
    for(int i = 0; i < n/2; i++){
        if(cs.charAt(i) ! = cs.charAt(n-i-1)) {return false; }}return true;
}
// Whether it is a letter or a number
public boolean check(char c){
    return c>=48&&c<=57 || c>=65&&c<=90 || c>=97&&c<=122;
}
// Change the uppercase to lowercase
public char change(char c){
    return c>=65&&c<=90 ? c+=32 : c;
}
Copy the code

Solution two: Detail optimization (double pointer)

We just used two loops, and the first one filters the alphanumeric ones. The second loop checks if the alphanumeric string is repeated. It’s actually redundant, so we can just do it in the first loop, and the ultimate goal is to see if the alphanumeric is palindromic but we don’t have to pull it out and do it again. That reduces one container and one traversal.

public boolean isPalindrome(String s) {
    if(s == null || s.length() == 0) return true;
    char[] arr = s.toCharArray();
    int n = arr.length;
    
    int start = 0;
    int end = n - 1;
    while(start < end){
        while(start < end && ! check(arr[start])){ start++; }while(start < end && ! check(arr[end])){ end--; }if(change(arr[start])! =change(arr[end])){return false;
        }
        start++;
        end--;
    }
    return true;
}
// Whether it is a letter or a number
public boolean check(char c){
    return c>=48&&c<=57 || c>=65&&c<=90 || c>=97&&c<=122;
}
// Change the uppercase to lowercase
public char change(char c){
    return c>=65&&c<=90 ? c+=32 : c;
}
Copy the code

Solution three: stack

We all know that stack is LIFO (LIFO), a kind of data structure. Here we can use arrays to implement stacks to complete the basic four methods

class Stack<E>{
    List<E> arr = new ArrayList();
    int top = -1;        
    void push(E c){
        arr.add(++top,c);
    }
    E pop(a){
        E c = peek();
        arr.remove(top--);
        return c;
    }
    E peek(a){
        return arr.get(top);
    }
    boolean isEmpty(a){
        return top < 0; }}Copy the code
public boolean isPalindrome(String s) {
    if(s == null || s.length() == 0) return true;
    char[] arr = s.toCharArray();
    int n = arr.length;
    Stack<Character> stack = new Stack<>();
    List<Character> list = new ArrayList<>();
        
    for (int i = 0; i < n; i++) {
        char c = arr[i];
        if(check(c)){ stack.push(change(c)); list.add(change(c)); }}int index = 0;
    while(! stack.isEmpty()){if(stack.pop() ! = list.get(index++))return false;
    }
    return true;
}
Copy the code

conclusion

Palindrome strings are handled in the same general way as double Pointers, reversals, or stacks. The Character class provides a method for determining whether it is a number or letter and a method for capitalization. I wrote the check(char c) and change(char C) methods separately above.

isLetterOrDigit(char c)
toLowerCase(char c)
Copy the code

If you use the Java class library you have a direct inversion method and of course there’s also a traversal, inversion and comparison. Of course, the efficiency is relatively low can refer to

//cs is the extracted alphanumeric string
String fz = cs.reverse().toString();
return cs.equals(fz);
Copy the code

In general, there are many ways to implement this, but dual Pointers are better for the efficiency of the implementation itself.

String of LeetCode daily: 125 validation palindrome string | creator training camp The campaign is under way…