Topic Description (Easy Difficulty)

Determines whether a string is a palindrome, ignoring characters other than letters and numbers.

Method a

Two Pointers, one from the beginning and one from the tail. Check whether the characters of the two Pointers are equal and skip the invalid characters. Note that the two Pointers do not need to be traversed from beginning to end. When the two Pointers meet, it means that the string is palindrome.

It is also important to note that ‘A’ == ‘A’, i.e. uppercase and lowercase letters are the same.

public boolean isPalindrome(String s) {
    int len = s.length();
    s = s.toLowerCase(); // All changes to lowercase
    int i = 0, j = len - 1;
    while (i < j) {
        // Skip illegal characters
        while(! isAlphanumeric(s.charAt(i))) { i++;// Matches a blank string like "" to prevent transgressions
            if (i == len) {
                return true; }}while(! isAlphanumeric(s.charAt(j))) { j--; }if(s.charAt(i) ! = s.charAt(j)) {return false;
        }
        i++;
        j--;
    }
    return true; 
}

private boolean isAlphanumeric(char c) {
    if ('a' <= c && c <= 'z' || 'A' <= c && c <= 'Z' || '0' <= c && c <= '9') {
        return true;
    }
    return false;
}  
Copy the code

Method 2

Above is the general idea, but here is another idea.

Above in order to deal with the problem of upper and lower case letters, first all unified to lowercase. To find an illegal character, you need to determine whether the character is in the legal range each time.

Here’s a trick that maps ‘0’ to ‘9’ to 1 to 10, ‘A’ to ‘z’ to 11 to 36, ‘a’ to ‘z’ to 11 to 36. Then store all the digits and letters in a char array, and any characters that are not stored are mapped to 0 by default.

In this case, you only need to determine whether each letter in the string maps to the same number. If it is 0, it means that it is an invalid character.

private static final char[] charMap = new char[256];

static {
    // map '0' to '9'
    for (int i = 0; i < 10; i++) {
        charMap[i + '0'] = (char) (1 + i); // numeric
    }
    // Map 'a' to 'z' and 'a' to 'z'
    for (int i = 0; i < 26; i++) {
        charMap[i + 'a'] = charMap[i + 'A'] = (char) (11+ i); }}public boolean isPalindrome(String s) {
    char[] pChars = s.toCharArray();
    int start = 0, end = pChars.length - 1;
    char cS, cE;
    while (start < end) {
        // Get the mapped number
        cS = charMap[pChars[start]];
        cE = charMap[pChars[end]];
        if(cS ! =0&& cE ! =0) {
            if(cS ! = cE)return false;
            start++;
            end--;
        } else {
            if (cS == 0)
                start++;
            if (cE == 0) end--; }}return true;
}
Copy the code

The total

It’s a very simple problem, but the thing to notice about solution two is that the idea of mapping all letters, both upper and lower case letters to the same number, saves a lot of work, speeds up a little bit. You can also do problem 5, given a string, find the longest substring of the loop. The horse-drawn cart algorithm described in the section is really too strong.

See Leetcode.Wang for more details on popular problems.