首页 > itarticle > 125. valid palindrome

125. valid palindrome

admin 11月 13, 2020 0


Leetcode
Two Pointers
String

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

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

Example 2:

Input: "race a car"
Output: false

分析¶

确认字符串是否为有效的回文。这道题目思路还是很简单的。第一步，判断字符是否有效；第二步，比较有效的字符是否左右对称。

public boolean isPalindrome(String s) {
    // length of the string
    int n = s.length();

    // special occasion
    if (n < 2) return true;

    char[] charArray = s.toLowerCase().toCharArray();
    char cur;
    int left = -1, right = n;
    while (true) {
        while (!validAlphanumeric(charArray[++left]))
            if (left == n - 1) return true;
        while (!validAlphanumeric(charArray[--right])){}

        if (left >= right) break;
        if (charArray[left] != charArray[right])
            return false;
    }
    return true;
}

/**
 * check if it is a valid alphanumeric characters
 * return false if not.
 */
private boolean validAlphanumeric(char c) {
    if (c >= 'a' && c <= 'z') 
        return true;
    else if (c >= '0' && c <= '9')
        return true;

    return false;   
}