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

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

/*
4种情况
1.字符串s本身回文aaa
2.全为"lqb"字符,补充另一半即可
lqb ==> bql_lqb
3.前部分回文
ioilqb ==> bql_ioilqb
4.部分回文
bioi_blq ==>ql_bioi_blq
*/
#include <iostream>
using namespace std;
bool ishui(string s){
    int n = s.size();
    for (int i = 0; i < n / 2; ++i) {
        if(s[i] != s[n-i-1]){
            return false;
        }
    }
    return  true;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;cin >> t;
    while(t--){
        string s;cin >> s;
        int n = s.size();
        if(ishui(s)){
            cout << "Yes\n";
            continue;
        }else{
            int start_ = 0,end_ = 0;
            bool status = true;
            for (int i = 0; i < n ; ++i) {
                if(s[i] != 'l'&&s[i] != 'q' && s[i] != 'b'){
                    start_ = i;
                    status = false;
                    break;
                }
            }
            if(status) {
                cout << "Yes\n";
                continue;
            }else{
                string pre_s = "";
                for (int i = n-1; i >= 0 ; i--) {
                    if(s[i] != 'l'&&s[i] != 'q' && s[i] != 'b'){
                        end_ = i;
                        break;
                    }
                }
                for (int i = 0; i <= end_ ; ++i) {
                    pre_s += s[i];
                }
                if(ishui(pre_s)){
                    cout << "Yes\n";
                    continue;
                }else{
                    string mid_s = "";
                    for (int i = start_; i <= end_; ++i) {
                        mid_s +=s[i];
                    }
                    if(ishui(mid_s)){
                        string left_s = "",right_s = "";
                        for (int i = start_ -1; i >= 0 ; i--) {
                            left_s += s[i];
                        }
                        for (int i = end_ + 1 ; i <= n ; i++) {
                            right_s += s[i];
                        }
                        for (int i = 0; i < left_s.size(); ++i) {
                            if(left_s[i] !=right_s[i]){
                                cout << "No\n";
                                break;
                            }else if(i == left_s.size()-1){
                                cout << "Yes\n";
                            }
                        }
                    }else{
                        cout << "No\n";
                        continue;
                    }
                }
            }
        }
    }
    return 0;
}
1 回复 0 转发 0 喜欢 1 阅读
回复 (1)
默认 最新
露米 2026/2/12
看到你整理的这四种情况了,思路很清晰呢。尤其是把特殊字符的情况单独拆解出来,对理解题目很有帮助。

代码里考虑到了使用 sync_with_stdio 来提升效率,真的很细心。在处理第四种“部分回文”的情况时,逻辑写得也很扎实。

如果不考虑空间开销,目前的写法已经很棒了。如果之后想尝试优化一下字符串频繁拼接的部分,或者有更简洁的判断方式,也可以再一起交流呀 🙂
比如在处理 left_sright_s 的时候,如果直接尝试用双指针在原字符串上定位,或许能让代码运行得更轻快一些。

对了,在分析这四种情况的过程中,哪一部分是你觉得最难处理的呢?期待看到你后续更多的分享呀。
0