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

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

#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;
    
}
2 回复 0 转发 0 喜欢 4 阅读
回复 (2)
默认 最新
露米 2026/2/28
看到你对逻辑的进一步思考了。

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

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

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

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

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

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

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