程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode 125 Valid Palindrome(有效回文)(*)

LeetCode 125 Valid Palindrome(有效回文)(*)

編輯:關於C++

翻譯

給定一個字符串,確定它是否是回文的,僅僅考慮其中的數字和字符並忽略其他。

例如,
“A man, a plan, a canal: Pannama” 是回文的。
“race a car” 不是回文的

批注:
你是否考慮了字符串可能為空?這種面試的時候是一個好問題。

對於這問題的意圖,我們定義空字符串是回文的。

原文

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.

分析

題目解出來並不是很難,不過需要細心不過還是會出錯。

第一步就是要從原字符串中的干擾去掉,也就是只保留字母,這可以通過ascii來判斷。

然後構造出新的字符串,再判斷這個新字符串是否是回文的就好了。

然而我也還是錯了,首先我沒想清楚題目的例子,”aA”也是回文的。

再一次修改之後我還是錯了,因為題目的alphanumeric是字母數字均包含了,我一開始翻譯的就是字母,後來上文的翻譯也修改了。

於是我確定徹底的改革,將功能獨立出來,然而代碼好長了,但是很清晰:

代碼

class Solution {
public:
    bool isAlpha(char c) {
        int ascii = (int)c;
        if ((ascii >= 65 && ascii <= 90) || (ascii >= 97 && ascii <= 122))
            return true;
        else return false;
    }    
    bool isNumber(char c) {
        int ascii = (int)c;
        if (ascii >= 48 && ascii <= 57)
            return true;
        else return false;
    }       
    bool isAlphaAndNumber(char c1, char c2) {
        if ((isAlpha(c1) && isNumber(c2)) || (isAlpha(c2) && isNumber(c1)))
            return true;
        else return false;
    }       
    bool isPalindrome(string s) {
        if (s.size() == 0) return true;
        string newStr = "";
        for (int i = 0; i < s.size(); ++i) {
            // 只取出其中的字母和數字
            if (isAlpha(s[i]) || isNumber(s[i]))
                newStr += s[i];
        }
        for (int i = 0; i < newStr.size() / 2; ++i) {
            // 兩者一個是字母、一個是數字
            if (isAlphaAndNumber(newStr[i], newStr[newStr.size() - i - 1]))
                return false;
            // 兩者均為數字
            else if (isNumber(newStr[i]) && isNumber(newStr[newStr.size() - i - 1])) {
                // 判斷是否是同一個數字
                if (newStr[i] != newStr[newStr.size() - i - 1])
                    return false;
            }
            // 兩者均為字母
            else {
                // 前面判斷是否是同一個字母,後面判斷是否是互為大小寫
                if (newStr[i] != newStr[newStr.size() - i - 1] && abs((int)newStr[i] - (int)newStr[newStr.size() - i - 1]) != 32)
                    return false;
            }
        }
        return true;
    }                           
};

進階

一想到ascii就忘了還有toupper這些函數了,別人寫的……

class Solution {
public:
    bool isPalindrome(string s) {
        int l = 0, r = s.size() - 1;
        while(l <= r){
            while(!isalnum(s[l]) && l < r) l++;
            while(!isalnum(s[r]) && l < r) r--;
            if(toupper(s[l]) != toupper(s[r])) return false;
            l++, r--;
        }
        return true;
    }
};
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved