# Valid Palindrome

## Question

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

**Notice**

Have you consider that the string might be empty? This is a good question to ask during an interview.

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

**Example**

`"A man, a plan, a canal: Panama"` is a palindrome.

`"race a car"` is not a palindrome.

**Challenge**

O(n) time without extra memory.

**Tags**

String Two Pointers Facebook Zenefits Uber

**Related Problems**

Medium Palindrome Linked List\
Medium Longest Palindromic Substring

## Analysis

根据Palindrome本身对称性的特点，比较适合用two pointers的方法来解决，因为这里对valid palindrome的定义不考虑非字母和数字的字符，就需要在移动pointers时候注意条件判断，除了下标的边界，还有`isAlphanumeric()`来判定是否为字母和数字。isAlphanumeric()可以用内置函数`Character.isLetter()`和`Character.isDigit()`，也可以根据`char` ASCII码的定义写出。补充：还有一个专门内置函数：`Character.isLetterOrDigit()`，用`Character.toLowerCase()`统一大小写。

Test Cases需要考虑周到，比如：

`" "`\
`"a..."`\
`"...a"`\
`"a.a"`

## Solution

```java
public class Solution {
    /**
     * @param s A string
     * @return Whether the string is a valid palindrome
     */
    public boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        int i = 0;
        int j = s.length() - 1;

        while (i < j) {
            while (i < s.length() && !isAlphanumeric(s.charAt(i))) {
                i++;
            }
            if (i == s.length()) {
                return true;
            }
            while (j >= 0 && !isAlphanumeric(s.charAt(j))) {
                j--;
            }

            if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {
                break;
            } else {
                i++;
                j--;
            }
        }
        return (j <= i);
    }

    public boolean isAlphanumeric(char ch) {
        // return Character.isLetter(ch) || Character.isDigit(ch);
        boolean result = (ch <= 'z' && ch >= 'a') ||
            (ch <= 'Z' && ch >= 'A') ||
            (ch <= '9' && ch >= '0');
        return result;

    }
}
```

Another implementation of isAlphanumeric()

```java
    // Use Character methods isLetter(), isDigit()
    private boolean isAlphanumeric (char c) {
        return Character.isLetter(c) || Character.isDigit(c);
    }
```

A verbose way - filter alphanumeric first, then start expanding from middle point of the new string

Time - O(n), Space O(n)

```java
class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (Character.isLetter(ch)) {
                sb.append(Character.toLowerCase(ch));
            } else if (Character.isDigit(ch)) {
                sb.append(ch);
            }
        }

        String t = sb.toString();
        System.out.println(t);

        int i, j;

        if (t.length() % 2 == 0) {
            // even number
            i = (t.length() - 1) / 2;
            j = i + 1;

        } else {
            // odd number
            i = t.length() / 2;
            j = i;
        }
        while (i >= 0 && j < t.length()) {
            if (t.charAt(i) != t.charAt(j)) {
                return false;
            }
            i--;
            j++;
        }

        return true;
    }
}
```

**\***(**Preferred**) **A concise, one pass (4ms, 92.32%)**

善用`Character.isLetterOrDigit()`函数，跳过非alphanumeric的字符，然后在比较时，用`Character.toLowerCase()`统一大小写。

```java
class Solution {
    public boolean isPalindrome(String s) {
        int l = 0;
        int r = s.length() - 1;
        while (l < r) {
            char lChar = s.charAt(l);
            char rChar = s.charAt(r);
            if (!Character.isLetterOrDigit(lChar)) {
                l++;
            } else if (!Character.isLetterOrDigit(rChar)) {
                r--;
            } else {
                if (Character.toLowerCase(lChar) != Character.toLowerCase(rChar)) {
                    return false;
                }
                l++;
                r--;
            }
        }
        return true;

    }
}
```

## Reference

<http://www.jiuzhang.com/solutions/valid-palindrome/>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/two_pointers/valid_palindrome.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.