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; } }