2017-05-15 22:07:13 +0000   |     algorithm leetcode two pointers string   |   Viewed times   |    

题目

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.

利用首尾两个指针,

一个指针指lo向头部0,一个指针hi指向尾部length-1。同时向中心推进。以lo > hi为终止条件。

代码

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

结果

银弹! valid-palindrome-1