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

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

#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;
    
}
4 回复 0 转发 0 喜欢 8 阅读
回复 (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