【C++】125 验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

#include <iostream>
#include <cctype>
using namespace std;

bool isPalindrome(string s) {
    // 将字符串中的大写字母转换为小写字母
    for (char &c : s) {
        if (isupper(c)) {
            c = tolower(c);
        }
    }

    // 移除所有非字母数字字符
    string filteredStr = "";
    for (char c : s) {
        if (isalnum(c)) {
            filteredStr += c;
        }
    }

    // 检查短语是否为回文串
    int left = 0, right = filteredStr.length() - 1;
    while (left < right) {
        if (filteredStr[left] != filteredStr[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

int main() {
    string s = "A man, a plan, a canal: Panama";
    if (isPalindrome(s)) {
        cout << "True" << endl;
    } else {
        cout << "False" << endl;
    }
    return 0;
}

时间复杂度分析：

大写字母转换为小写字母的循环遍历时间复杂度为 O(n)，其中 n 为字符串 s 的长度。
移除非字母数字字符的循环遍历时间复杂度同样为 O(n)。
检查回文串的过程中，使用了双指针法，时间复杂度为 O(n/2)，即 O(n)。
总体来说，这段代码的时间复杂度为 O(n)。

空间复杂度分析：

新建了一个字符串 filteredStr 用于存储移除非字母数字字符后的字符串，其长度最多为原字符串 s 的长度，因此空间复杂度为 O(n)。
除此之外，没有使用额外的数据结构，因此其他空间占用可以忽略不计。
总体来说，这段代码的空间复杂度为 O(n)。
综上所述，该代码的时间复杂度为 O(n)，空间复杂度也为 O(n)。

tips:
isalnum() 是 C++ 中的一个函数，用于判断一个字符是否为字母或数字字符。函数的原型如下：

int isalnum(int c);

它接受一个字符作为参数，并返回一个非零值（通常为1），如果该字符是一个字母（即 A-Z 或 a-z）或数字（即 0-9），否则返回0。

这个函数通常用于字符分类，用于过滤字符串中的非字母数字字符。

原文地址：https://blog.csdn.net/ZSZ_shsf/article/details/137693989

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！