题目：

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

For example,

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

"race a car" is not a palindrome.

Note:

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.

链接： 

题解：

根据题意用两个指针对冲法。

Time Complexity - O(n)， Space Complexity - O(1)。

public class Solution {    public boolean isPalindrome(String s) {        if(s == null)            return true;        int lo = 0, hi = s.length() - 1;        s = s.toLowerCase();                while(lo <= hi) {            if(!isAlphanumeric(s.charAt(lo))) {                lo++;                continue;            }            if(!isAlphanumeric(s.charAt(hi))) {                hi--;                continue;            }            if(s.charAt(lo) != s.charAt(hi))                return false;            else {                lo++;                hi--;            }        }                return true;    }        private boolean isAlphanumeric(char c) {        if(Character.isDigit(c) || Character.isLetter(c))            return true;        else            return false;    }}

 

二刷：

方法和一刷一样，双指针向中间夹逼，忽略非alphanumeric value，

Java:

Time Complexity - O(n)， Space Complexity - O(1)。

public class Solution {    public boolean isPalindrome(String s) {        if (s == null) {            return false;        }        s = s.toLowerCase();        int lo = 0, hi = s.length() - 1;        while (lo <= hi) {            while (lo < hi && !isDigitOrAlphabet(s.charAt(lo))) {                lo++;            }                while (lo < hi && !isDigitOrAlphabet(s.charAt(hi))) {                hi--;            }            if (s.charAt(lo) == s.charAt(hi)) {                lo++;                hi--;            } else {                return false;            }        }        return true;    }        private boolean isDigitOrAlphabet(char c) {        if ((c <= '9' && c >= '0') || (c <= 'z' && c >= 'a')) {            return true;        }        return false;    }    }

 

使用库方法的

public class Solution {    public boolean isPalindrome(String s) {        if (s == null) {            return false;        }        int lo = 0, hi = s.length() - 1;        while (lo <= hi) {            while (lo < hi && !Character.isLetterOrDigit(s.charAt(lo))) {                lo++;            }                while (lo < hi && !Character.isLetterOrDigit(s.charAt(hi))) {                hi--;            }            if (Character.toLowerCase(s.charAt(lo)) == Character.toLowerCase(s.charAt(hi))) {                lo++;                hi--;            } else {                return false;            }        }        return true;    }}

 

三刷:

Java:

public class Solution {    public boolean isPalindrome(String s) {        if (s == null) return false;        int lo = 0, hi = s.length() - 1;        while (lo <= hi) {            char loChar = s.charAt(lo);            if (!Character.isLetterOrDigit(loChar)) {                lo++;                continue;            }            char hiChar = s.charAt(hi);            if (!Character.isLetterOrDigit(hiChar)) {                hi--;                continue;            }            if (Character.toLowerCase(loChar) != Character.toLowerCase(hiChar)) return false;            lo++;            hi--;        }        return true;    }}

 

 

Reference:

https://leetcode.com/discuss/23989/accepted-pretty-java-solution-271ms