MENU

LeetCode125. Valid Palindrome(模拟 / 回文串)

2019 年 02 月 04 日 • 阅读: 784 • LeetCode阅读设置

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日 星期一