leetcode筆記：Valid Palindrome

leetcode筆記：Valid Palindrome

一.題目描述

二.解題技巧

這道題考察回文數（palindrome），這一概念起源於在數學中一類數字，這類數字擁有這樣的特征：

設n是一任意自然數。若將n的各位數字反向排列所得自然數n1與n相等，則稱n為一回文數。例如，若n=1234321，則稱n為一回文數；但若n=1234567，則n不是回文數。

同理，可以定義英文/中文的回文數，概念和以上的類似，本題就是檢測字符串是否為回文數。與數字回文不同的是，題目中給出的英文句子/短語包含空格及標點符號，因此需要在算法設計時加多一層判斷，可能會用到以下函數：

isalpha()  // 如果參數是一個字母，返回一個非零數；否則返回為0
isalnum()  // 如果參數是一個字母或數字，返回一個非零數；否則返回為0
isdigit()  // 如果參數是一個數字（0-9）返回一個非零數；否則返回為0

若不要求區分字符串的大小寫問題，可以加入以下函數：

transform（string.begin(),string.end(),string.begin(),toupper);  // 將字符串中的內容轉換為大寫字母

transform（string.begin(),string.end(),string.begin(),tolower);  // 將字符串中的內容轉換為小寫字母

題目說明，空字符串也可判定為回文，除此之外，該題目並沒有很復雜的邏輯問題和邊界條件。

三.示例代碼

#include 
#include 
using std::string;

class Solution
{
public:
    bool validPalindrome(string s)
    {
        if (s == )
            return true;
        auto index_start = s.begin(), index_end = prev(s.end());
        while (index_start < index_end)
        {
            if (!isalpha(*index_start))
                index_start++;
            else if (!isalpha(*index_end))
                index_end--;
            else if (*index_start == *index_end)
            {
                index_start++;
                index_end--;
            }
            else return false;
        }
        return true;
    }
};

四.一個示例結果

輸入回文字符串：

輸入非回文字符串：