Sword finger offer II 018 Valid palindrome

A word summary

Double pointers traverse from both ends to the center at the same time , If not, return to false.

subject

Given a string s , verification s Whether it is Palindrome string , Consider only alphabetic and numeric characters , The case of letters can be ignored .

In this question , Define an empty string as a valid Palindrome string .

Ideas

We need to ignore characters other than letters and numbers .

You can traverse each character of the string first , Do a pretreatment first . Preprocessing needs to remove non alphanumeric characters , Then unify the upper case letters into lower case .

Then use two pointers to traverse from both sides to the center , Check whether the elements corresponding to the two pointers are consistent .

This is where ASCII code , Refer to the sword finger Offer II 002. The extended knowledge of binary addition .

Solution 1 ： Preprocessing strings , The double pointer traverses toward the center

Code

public boolean isPalindrome(String s) {
    
    StringBuilder sb = new StringBuilder();
    for (char c : s.toCharArray()) {
    
        if ((c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z')) {
    
            sb.append(c);
        }
    }

    String finalStr = sb.toString().toLowerCase();
    if ("".equals(finalStr)) {
    
        return true;
    }
    for (int i = 0; i <= finalStr.length() / 2 - 1; i++) {
    
        if (finalStr.charAt(i) != finalStr.charAt(finalStr.length() - i - 1)) {
    
            return false;
        }
    }

    return true;
}

Solution 2 ： Direct double pointer traversal to the center

Logic

For the first solution , You can start double pointer traversal to the center directly , A pretreatment process is omitted , While traversing , To determine whether it is a number or a letter .

Code

    public boolean isPalindrome(String s) {
    
        String s1 = s.toLowerCase();
        int left = 0;
        int right = s1.length() - 1;
        while (left < right) {
    
            char leftC = s1.charAt(left);
            char rightC = s1.charAt(right);
            if (needRemove(leftC)) {
    
                left++;
                continue;
            }
            if (needRemove(rightC)) {
    
                right--;
                continue;
            }
            if (leftC != rightC) {
    
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public boolean needRemove(char c){
    
        return (c < '0' || c > '9') && (c < 'a' || c > 'z');
    }