[LeetCode]125.Valid Palindrome-阿里云开发者社区

[LeetCode]125.Valid Palindrome

2013-12-09 1774

版权

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

简介：

【题目】

Valid Palindrome

Total Accepted: 3479 Total Submissions: 16532 My Submissions

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.

【代码】

【方法1】

/*********************************
*   日期：2013-12-09
*   作者：SJF0115
*   题目: 125.Valid Palindrome
*   来源：http://oj.leetcode.com/problems/valid-palindrome/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
class Solution {
public:
    bool isStr(char &ch){
        //数字
        if(ch >= '0' && ch <= '9'){
            return true;
        }
        //小写字母
        else if(ch >= 'a' && ch <= 'z'){
            return true;
        }
        //大写字母
        else if(ch >= 'A' && ch <= 'Z'){
            //转换为小写
            ch += 32;
            return true;
        }
        return false;
    }

    bool isPalindrome(string s){
        int i,j;
        int len = s.length();
        if(len == 0){
            return true;
        }
        string str = "";
        //去掉非数字字母字符
        for(i = 0; i < len; i++){
            if(isStr(s[i])){
                str += s[i];
            }
        }
        len = str.length();
        for(i = 0,j = len - 1; i < j; i++,j--){
            if(str[i] != str[j]){
                return false;
            }
        }
        return true;
    }
};

【方法2】

class Solution {
public:
    bool isStr(char &ch){
        //数字
        if(ch >= '0' && ch <= '9'){
            return true;
        }
        //小写字母
        else if(ch >= 'a' && ch <= 'z'){
            return true;
        }
        //大写字母
        else if(ch >= 'A' && ch <= 'Z'){
            //转换为小写
            ch += 32;
            return true;
        }
        return false;
    }

    bool isPalindrome(string s){
        int i,j;
        int len = s.length();
        if(len == 0){
            return true;
        }
        len = s.length();
        for(i = 0,j = len - 1; i < j;){
            if(!isStr(s[i])){
                i++;
                continue;
            }
            if(!isStr(s[j])){
                j--;
                continue;
            }
            if(s[i] != s[j]){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
};

【测试】

/*********************************
*   日期：2013-12-09
*   作者：SJF0115
*   题号: 题目: Valid Palindrome
*   来源：http://oj.leetcode.com/problems/valid-palindrome/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include <iostream>
#include <stdio.h>
using namespace std;

class Solution {
public:
    bool isStr(char &ch){
        //数字
        if(ch >= '0' && ch <= '9'){
            return true;
        }
        //小写字母
        else if(ch >= 'a' && ch <= 'z'){
            return true;
        }
        //大写字母
        else if(ch >= 'A' && ch <= 'Z'){
            //转换为小写
            ch += 32;
            return true;
        }
        return false;
    }

    bool isPalindrome(string s){
        int i,j;
        int len = s.length();
        if(len == 0){
            return true;
        }
        string str = "";
        //去掉非数字字母字符
        for(i = 0; i < len; i++){
            if(isStr(s[i])){
                str += s[i];
            }
        }
        len = str.length();
        for(i = 0,j = len - 1; i < j; i++,j--){
            if(str[i] != str[j]){
                return false;
            }
        }
        return true;
    }
};
int main() {
    bool result;
    string str = "A man, a plan, a canal: Panama";
    //string str = "race a car";
    Solution solution;
    result = solution.isPalindrome(str);
    if(result){
        printf("This is a Palindrome\n");
    }
    else{
        printf("sorry\n");
    }
    return 0;
}