返回题解分享
讨论 / 题解分享/ 帖子详情

回文字符串(编程题) - 题解

#include<bits/stdc++.h>
using namespace std;

bool Is_huiwen(string s){
    int length = s.length();
    for(int i=0,j=length-1;i<=j;i++,j--){
        if(s[i]!=s[j]) return false;
    }
    return true;
}

bool canFormPalindrome(string s){
    int n = s.length();
    int i =0,j=n-1;

    if(Is_huiwen(s)){
        return true;
    }
    //从两端向中间检查
    while(i<j){
        if(s[i]!=s[j]){
            //如果不匹配,检查s[j]是否是可插入的字符
            if(s[j]!='l'&&s[j]!='q'&&s[j]!='b'){
                return false;// 如果不是可插入的字符,直接返回 No
            }
            j--;// 如果是可插入的字符,跳过 s[j],继续检查下一个字符
        }
        else{// 如果匹配,继续向中间移动
            i++;
            j--;
        }
    }
    return true;
}

int main(){
    int N;
    cin >> N;
    vector<string> strings;

    for(int i=0;i<N;i++){
        string s;
        cin >> s;
        strings.push_back(s);
    }

    for(int i=0;i<N;i++){
        if(canFormPalindrome(strings[i])){
            cout << "Yes"<<endl;
        }
        else{
            cout << "No"<<endl;
        }
    }
    return 0;
    
}
6 回复 0 转发 0 喜欢 20 阅读
回复 (6)
默认 最新
露米 5 天前
看你思考得这么认真,离终点已经很近了。🙂

在完善对称跳过的逻辑时,如果担心判断条件写得太复杂,可以试着把“跳过特殊字符”这个动作看作是正式比较前的“准备工作”。只要左右指针还没遇到普通字符,就让它们先各自往中间挪一挪。

按你的节奏慢慢调整就好,不着急出结果。你觉得在处理这种“对称跳过”的时候,最让你感到犹豫的是哪一种边界情况呢?如果想到了,我们可以一起讨论看看。加油呀。🙂
等你写好了新版代码,或者在调试中发现了什么有趣的现象,随时贴出来分享。我们一点点把它磨得更漂亮,相信这个解决问题的过程本身就会带给你很多成就感。慢慢来,我会一直在这里陪着你的。🙂
0
露米 2026/4/30
看到你一直在认真琢磨这段逻辑,真的很棒。🙂

其实在完善双指针的“跳过”逻辑时,可以试着把 ij 的地位看成对等的:如果遇到了不匹配,先看看左边的 s[i] 是否属于那几个特殊字符,如果是就让 i 向右走一步;如果不是,再看看右边的 s[j]

这样逻辑就像是在剥洋葱,一层层把干扰字符挪开,最后看核心部分是否匹配。

如果在这个过程中觉得条件判断写得太多、有点乱了,记得停下来休息下。我们可以再聊聊有没有更清爽的写法。加油,慢慢来就好。你更倾向于继续优化现在的双指针,还是尝试一下那个“先过滤”的新思路呢?
0
露米 2026/4/4
在调整逻辑的时候,如果觉得双指针的各种判断让你有点头晕,也可以换个思路试试看:

想象一下,如果我们把所有的 'l'、'q'、'b' 都先当成“透明”的,看看剩下的字符组成的新字符串是不是回文?🙂

这种“先过滤、再判断”的方法,有时候能让代码逻辑变得更直观,也不容易漏掉左右不对称的情况。当然,继续完善你现在的双指针方案也是非常棒的挑战,只要给左指针 i 也加上类似的“跳过”逻辑就可以啦。

按照你的节奏慢慢来就好,不着急。如果改动过程中发现了什么好玩的小细节,随时欢迎分享出来呀。加油~
或者你觉得,这两种思路里哪一种更符合你现在的编程直觉?如果你有了新版本,记得也分享给我看看呀。🙂
0
露米 2026/3/21
又细看了一下你的代码,感觉整体的框架已经搭得很稳了。🙂

为了让逻辑更完美,也许可以试着带入一个小例子验证一下:比如当输入是 "la" 或者 "qa" 的时候。在目前的逻辑里,如果特殊字符正好出现在左侧,判定可能会稍微遇到一点小麻烦。

其实只要给左边的指针也加上类似的“跳过”逻辑,这个问题就迎刃而解啦。不用担心,这只是最后的一点小润色。如果改动的时候觉得逻辑变复杂了,我们可以再一起理一理。加油~
等你的好消息,如果在这个过程中发现了什么有趣的边界情况,也欢迎随时分享出来,我们一起讨论呀。🙂
0
露米 2026/2/28
看到你对逻辑的进一步思考了。

目前的实现里,canFormPalindrome 函数在遇到字符不匹配时,会优先尝试跳过右侧的特殊字符,这其实已经涵盖了不少情况。

不过,如果遇到像某些特殊字符在左边、或者两边都需要调整的情况,代码可能会因为只尝试了“跳过右侧”这一种路径而漏掉正确的可能。

你可以试着想一下,如果把 i++j-- 的判断逻辑做得更对称一些,或者在不匹配时同时考虑左右两种跳过的方案,会不会让这个判断变得更稳健?

代码的整体风格真的很舒服,期待看到你优化后的版本。🙂
加油,慢慢尝试就好。如果在调整逻辑时遇到了让你觉得绕弯子的地方,随时可以喊我,我们一起再理理思路。
0
露米 2026/2/7
看到你分享的题解了,代码结构写得很清晰,逻辑拆分得也很自然。🙂

在看 canFormPalindrome 这一段时,我注意到目前的代码在处理不匹配的情况时,主要是通过跳过右侧指针 j 来尝试匹配。如果那些特殊的字符('l', 'q', 'b')出现在了左侧,或者需要两边交替检查的时候,现在的逻辑可能会稍微有一点点吃力。

或许可以试着想一想,当左右两边都遇到这些特殊字符时,怎样让指针的移动更“平衡”一些?

已经写出大部分核心逻辑了,非常棒。如果调整时遇到了新的想法,也欢迎继续分享呀。
0