LintCode题解|FB/Uber 最新OA高频题：有效回文串

描述

给定一个字符串，判断其是否为一个回文串。只考虑字母和数字，忽略大小写。

你是否考虑过，字符串有可能是空字符串？这是面试过程中，面试官常常会问的问题。
在这个题目中，我们将空字符串判定为有效回文。

样例

样例 1:

输入: "A man, a plan, a canal: Panama"
输出: true
解释: "amanaplanacanalpanama"

样例 2:

输入: "race a car"
输出: false
解释: "raceacar"

挑战
O(n) 时间复杂度，且不占用额外空间。

相关题目

题目解析

判断给定字符串是否是回文串，只需要比较ASCII码的字母和数字即可，其它符号跳过

首先介绍两个函数，在这里使用比较方便

int isalnum(int c);如果c是数字或大小写字母，返回true

int toupper(int c);将字符c转为大写

回文串左右是对称的，所以只需要从两边向中间推进判断

参考代码

public class Solution {
    public boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }

        int front = 0;
        int end = s.length() - 1;
        while (front < end) {
            while (front < s.length() && !isvalid(s.charAt(front))) { // nead to check range of a/b
                front++;
            }

            if (front == s.length()) { // for empty string “.,,,”     
                return true; 
            }           

            while (end >= 0 && ! isvalid(s.charAt(end))) { // same here, need to check border of a,b
                end--;
            }

            if (Character.toLowerCase(s.charAt(front)) != Character.toLowerCase(s.charAt(end))) {
                break;
            } else {
                front++;
                end--;
            }
        }

        return end <= front; 
    }

    private boolean isvalid (char c) {
        return Character.isLetter(c) || Character.isDigit(c);
    }
}