开发者社区> 李博 bluemind> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

[LintCode] 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.

"A man, a plan, a canal: Panama" is a palindrome.

"race a car" is not a palindrome.

Challenge

O(n) time without extra memory.

LeetCode上的原题,请参见我之前的博客Valid Palindrome

解法一:

class Solution {
public:
    /**
     * @param s A string
     * @return Whether the string is a valid palindrome
     */
    bool isPalindrome(string& s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            if (!isAlNum(s[left])) ++left;
            else if (!isAlNum(s[right])) --right;
            else if ((s[left] + 32 - 'a') % 32 != (s[right] + 32 - 'a') % 32) return false;
            else {
                ++left; --right;
            }
        }
        return true;
    }
    bool isAlNum(char c) {
        if (c >= 'a' && c <= 'z') return true;
        if (c >= 'A' && c <= 'Z') return true;
        if (c >= '0' && c <= '9') return true;
        return false;
    }
};

解法二:

class Solution {
public:
    /**
     * @param s A string
     * @return Whether the string is a valid palindrome
     */
    bool isPalindrome(string& s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            if (!isalnum(s[left])) ++left;
            else if (!isalnum(s[right])) --right;
            else if ((s[left] + 32 - 'a') % 32 != (s[right] + 32 - 'a') % 32) return false;
            else {
                ++left; --right;
            }
        }
        return true;
    }
};

本文转自博客园Grandyang的博客,原文链接:验证回文字符串[LintCode] Valid Palindrome ,如需转载请自行联系原博主。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
LeetCode 125 Valid Palindrome(有效回文)(*)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50623165 翻译 给定一个字符串,确定它是否是回文的,仅仅考虑其中的数字和字符并忽略其他。
671 0
LeetCode 36 Valid Sudoku(有效数独)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50118647 翻译 数独板被部分填充,空格部分用'.'来填充。
636 0
+关注
李博 bluemind
云栖社区Java、Redis、MongoDB运营小编,有意合作请联系钉钉:15810436147
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载