【C++】B2124 判断字符串是否为回文

💯前言

• 判断一个字符串是否为回文是编程中常见的问题。回文字符串是指从前往后读与从后往前读都一样的字符串。例如，“abcdedcba” 就是回文，而 “abcde” 则不是。对于这类问题，我们可以采用多种不同的算法来解决。在本篇文章中，我们将分析四种不同的做法，并进行对比与优化，以帮助大家更好地理解如何判断字符串是否为回文。 C++ 参考手册

💯题目描述

B2124 判断字符串是否为回文

输入一个字符串，判断该字符串是否是回文。回文是指顺读和倒读都一样的字符串。

输入格式：

输入一行字符串，长度小于100。

输出格式：

如果字符串是回文，输出 yes；否则，输出 no。

样例：

输入：

abcdedcba

输出：

yes

💯方法一：我的第一种做法

思路

我的第一种做法是通过反转字符串来判断回文。首先，我们将原字符串反转，然后与原字符串进行比较。如果反转后的字符串与原字符串相等，则说明原字符串是回文。

代码实现

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

int main() {
    string s;
    cin >> s;  // 输入字符串

    int left = 0;
    int right = s.size() - 1;
    
    // 检查字符串的前半部分是否与后半部分对称
    while (left < right) {
        if (s[left] != s[right]) {
            cout << "no" << endl;  // 如果有不同字符，输出no
            return 0;
        }
        left++;
        right--;
    }
    
    cout << "yes" << endl;  // 如果没有不同字符，输出yes
    return 0;
}

解析

1. 反转字符串：通过双指针方式，使用 left 和 right 两个指针分别从字符串的两端开始向中间移动，逐个比较字符。
2. 时间复杂度：O(n)，其中 n 是字符串的长度。我们最多需要遍历字符串的前半部分，进行字符比较。
3. 空间复杂度：O(1)，仅使用了常数的空间来存储指针 left 和 right。

💯方法二：我的第二种做法

思路

在我的第二种做法中，我尝试使用了两次循环，首先将字符串反转到一个新的字符串 s2 中，然后通过逐字符对比 s2 和原字符串 s1 是否一致来判断回文。

代码实现

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

int main() {
    string s1, s2;
    while(cin >> s1) {
        s2.resize(s1.size());  
        for(int i = s1.size() - 1; i >= 0; i--) {
            s2[s1.size() - i - 1] = s1[i];
        }

        int temp = 1;
        for(int i = 0; i < s1.size(); i++) {
            if(s2[i] != s1[i]) {
                temp = 0;
                break;
            }
        }
        if(temp)
            cout << "yes" << endl;
        else
            cout << "no" << endl;
    }

    return 0;
}

解析

1. 字符串反转：首先创建一个 s2 字符串，并使用 for 循环反转 s1 字符串的内容，存储到 s2 中。
2. 回文判断：然后通过逐个字符对比 s2 和 s1，如果遇到不同的字符，则输出 no。
3. 存在问题：
   • s2 没有预先调整大小： s2 在反转前没有设置大小，可能会导致内存越界。可以通过 resize 来调整其大小。
   • 逻辑错误：break 的位置存在问题，导致判断逻辑不正确，跳出循环时判断不够精确。

改进建议

通过双指针法可以优化空间使用，并且避免了额外的字符串存储开销。具体改进后我们会在后面介绍。

💯方法三：老师的第一种做法

思路

老师的第一种做法采用了双指针法。这是一种非常高效的方法。通过两个指针，分别从字符串的两端开始，逐个比较字符，如果出现不同的字符，就可以直接返回 no，否则直到两个指针相遇时，输出 yes。

代码实现

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

int main() {
    string s;
    cin >> s;  // 输入字符串

    int left = 0;
    int right = s.size() - 1;

    while (left < right) {
        if (s[left] != s[right]) {
            cout << "no" << endl;  // 如果有不同字符，输出no
            return 0;
        }
        left++;
        right--;
    }

    cout << "yes" << endl;  // 如果没有不同字符，输出yes
    return 0;
}

解析

1. 双指针法：通过两个指针 left 和 right 从字符串的两端向中间逼近。每次比较 s[left] 和 s[right]，如果发现不相等，直接返回 no，否则继续向中间推进。
2. 时间复杂度：O(n)，每次最多需要遍历一次字符串的长度。
3. 空间复杂度：O(1)，只使用了常数空间来存储两个指针。

优点

1. 空间复杂度为 O(1)，避免了额外的空间开销。
2. 效率高，每次只进行一次字符比较，比反转字符串的方法更直接且高效。

💯方法四：老师的第二种做法

思路

老师的第二种做法使用了标准库中的 reverse 函数，将字符串反转后直接与原字符串进行比较。这是一种简洁的做法，但其空间复杂度稍高，因为需要额外的存储空间来保存反转后的字符串。

代码实现

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    string t = s;
    reverse(t.begin(), t.end());  // 反转字符串

    if (t == s) 
        cout << "yes" << endl;
    else
        cout << "no" << endl;

    return 0;
}

解析

1. 字符串反转：利用 reverse 函数将字符串 s 反转，并保存到 t 中。
2. 回文判断：通过直接比较反转后的字符串 t 和原字符串 s 是否相等来判断回文。

优点

1. 代码简洁：通过标准库函数，代码更加简洁和易懂。
2. 实现简单：使用 reverse 可以减少手动反转字符串的工作量。

缺点

1. 空间复杂度为 O(n)，因为需要额外的字符串 t 来存储反转后的字符串。

💯对比分析

1. 空间复杂度：
   • 我的第一种做法和老师的第一种做法都使用了 O(1) 空间，通过双指针来直接判断回文。
   • 我的第二种做法和老师的第二种做法需要额外的 O(n) 空间来存储反转后的字符串。
2. 时间复杂度：
   • 所有方法的时间复杂度均为 O(n)，其中 n 是字符串的长度。
3. 可读性与简洁性：
   • 我的第二种做法和老师的第二种做法通过反转字符串，代码简单易懂。
   • 我的第一种做法和老师的第一种做法更加高效，避免了不必要的空间开销。

💯扩展：空间优化和实际应用

在一些实际应用中，空间的使用往往是一个重要的考虑因素。如果我们能够通过优化算法减少空间复杂度，将会使得程序更高效。双指针法就是在空间优化方面的一个典型例子，它避免了反转字符串时的额外存储。

💯小结

本文通过分析四种不同的做法来判断字符串是否为回文，比较了它们在空间和时间复杂度上的表现。通过这几种做法，我们可以发现，双指针法在空间和时间上的优势较为明显，是最为推荐的解决方案。当然，对于小规模的问题，使用字符串反转的做法也不失为一种简洁高效的选择。

希望本篇文章能够帮助大家更好地理解字符串回文判断的不同做法，并能够根据实际问题选择合适的算法。