LintCode 415. Valid Palindrome 原创Java参考解答
问题描述
http://www.lintcode.com/en/problem/valid-palindrome/
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.
解题思路
题目是判断字符串是否为回文串。
- 根据题意，空的或长度为0的字符串也判断为true。
- 用Two Pointers方法，设一头一尾两个对撞型指针，从头从尾往中间走，遍历字符串每一个位置。判断头尾指针所在位置字符是否相同时，先转换该位置字符为小写。
- 头指针或尾指针遍历遇到非字母非数字情况则需要continue到下一个循环。必须用continue是因为，可能连续两个位置都是非字母非数字的字符。
参考代码
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) {
if (!Character.isLetterOrDigit(s.charAt(i))) {
i++;
continue;
}
if (!Character.isLetterOrDigit(s.charAt(j))) {
j--;
continue;
}
if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {
return false;
}
i++;
j--;
}
return true;
}
}