X

LEETCODE 125. Valid Palindrome 解题思路分析

题目大意:

验证回文串

给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。

说明:本题中,我们将空字符串定义为有效的回文串。

示例 1:

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

示例 2:

输入: "race a car"
输出: false

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=125

解题思路分析:

首先我们要直到如何判断回文,这是一个经典的判断方式。我们从字符串的最外层开始,判断两个端点的字符是否相同,如果不同直接返回false,反之,左指针加一,右指针减一,各向内移动一步继续判断是否相同,重复此过程一直到左指针大于等于右指针为止。

本题存在一些例外,字符串中只有数字和英文字母属于判断对象,除此之外的字符均为无效字符,不在检测范围内,因此遇到无效字符时需要继续移动指针,直到当前是有效字符为止。另外一点,本题中规定忽略大小写,因此当两指针指向的字符都是英文字母时,如果他们相同,肯定可以,如果他们之间差值的绝对值为32,说明他们也相同。

实现代码:

public boolean isPalindrome(String s) {
    // 为了提高效率,将字符串转为字符数组
    char[] arr=s.toCharArray();
    // 定义两指针,分别指向字符串最外层
    int l=0,r=arr.length-1;
    // 当左指针小于右指针时,保持循环
    while(l<r){
        // 如果当前左指针字符不是有效字符,左指针加一
        if(!isNum(arr[l])&&!isAlpha(arr[l])) {
            l++;
            continue;
        }
        // 如果当前右指针字符不是有效字符,右指针减一
        if(!isNum(arr[r])&&!isAlpha(arr[r])) {
            r--;
            continue;
        }
        // 如果当前两指针字符都是数字
        if(isNum(arr[l]) && isNum(arr[r])){
            // 如果两数字不同,返回false
            if(arr[l]!=arr[r]) return false;
        }
        // 如果当前两指针字符都是英文字母
        else if(isAlpha(arr[l]) && isAlpha(arr[r])){
            // 如果两字符不同并且两字符差值的绝对值不是32,返回false
            if(arr[l]!=arr[r]&&Math.abs(arr[l]-arr[r])!=32){
                return false;
            }
        }else{
            // 当前两指针一个是数字一个是字母时,返回false
            return false;
        }
        l++;
        r--;
    }
    return true;
}
boolean isNum(char c){
    return c>='0'&&c<='9';
}
boolean isBigCase(char c){
    return c>='A'&&c<='Z';
}
boolean isSmallCase(char c){
    return c>='a'&&c<='z';
}
boolean isAlpha(char c){
    return isBigCase(c)||isSmallCase(c);
}

本题解法执行时间为2ms。

Runtime: 2 ms, faster than 99.27% of Java online submissions for Valid Palindrome.

Memory Usage: 38.9 MB, less than 67.86% of Java online submissions for Valid Palindrome.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-125-valid-palindrome-解题思路分析/
Categories: leetcode
kwantong: