LeetCode125. Valid Palindrome（模拟 / 回文串）

LeetCode125. Valid Palindrome（模拟 / 回文串）

• Easy
• Accepted：311,266
• Submissions：1,041,834

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

Input: "race a car"
Output: false

---

链接

https://leetcode.com/problems/valid-palindrome/

题意

给定一个字符串，判断只包含字母和数字的部分字符是否为回文串。（空串为回文串）

题解

• 直接把是字母和数字的字符单独拉出来判断一下就行了。时间复杂度$O(n)​$

  • tolower()——toupper()【cctype常用库函数】
  • isupper()——islower()
  • isalnum()——isalpha()
• 使用对撞指针，分别指向首位，然后开始判断，注意过滤无用字符并分类讨论当前是数字还是字幕，数字要求相等，而字母不分大小写，时间复杂度$O(n)$

代码

// Accepted    8ms    1.3 MB
class Solution {
public:
    bool isPalindrome(string s) {
        string ss = "";
        int len = s.length();
        for (int i = 0; i < len; ++i)
        {
            if (isalpha(s[i])) // 字母，统一转为小写
                ss += tolower(s[i]);
            else if (isdigit(s[i])) // 数字
                ss += s[i];
        }
        int lens = ss.length();
        for (int i = 0; i < lens / 2; ++ i) // 单独判断
            if (ss[i] != ss[lens - 1 - i])
                return false;
        return true;
    }
};

• Runtime: 4 ms, faster than 100.00% of C++ online submissions for Valid Palindrome.
• Memory Usage: 1.1 MB, less than 57.06% of C++ online submissions for Valid Palindrome.

class Solution {
public:
    bool isPalindrome(string s) {
        int len = s.length();
        int l = 0, r = len - 1;
        while (l < r)
        {
            if (!isalnum(s[l])) // 过滤非数字和非字母字符
            {
                l++;
                continue;
            }
            if (!isalnum(s[r]))
            {
                r--;
                continue;
            }
            if ((isdigit(s[l]) || isdigit(s[r])) && s[l] != s[r]) // 数字要求相等
                return false;
            if (islower(s[l]) && s[l] != s[r] && s[l] != tolower(s[r])) // 大小写
                return false;
            if (isupper(s[l]) && s[l] != s[r] && s[l] != toupper(s[r]))
                return false;
            l++, r--;
        }
        return true;
    }
};

明显第二种解决要比第一种快一些。

---

The end.
2019年2月4日 星期一