阅读 28

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

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);
    }
}复制代码


关注下面的标签,发现更多相似文章
评论