LintCode 415. Valid Palindrome 原创Java参考解答

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


相关题目

LintCode All in One 原创题目讲解汇总

发表评论

您的电子邮箱地址不会被公开。