小红的回文串构造

2024-01-29 17:28

文章标签 构造回文小红

本文主要是介绍小红的回文串构造，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本题链接：登录—专业IT笔试面试备考平台_牛客网

题目：

样例1：

输入
`abba`

输出
baab

样例2：

输入
`aba`

输出
-1

思路：

由题意，题目保证给出的字符串是回文串的，所以我们只需要获取两个不同的字符的对应对称的两个坐标进行交换即可构造完毕。

这里有一个关键点，就是我们如何知道当前的下标 i 的堆成下标是多少？

关于 i 对称的下标，肯定有一个规律关系，其中对称又有两种方式。

其中奇数串对称：

奇数串对称:    dcabacd            偶数串对称：dcabbacd1234567                      12345678

观察对应的下标 i 就可以找出一定的规律为：

当前的下标 i 的对称下标 j  一定为：j = (s.length() % 2 ?  i + (s.length() / 2 - i) * 2: i + (s.length() / 2 - i) * 2 - 1);奇数串的时候 ：   j =   i + (s.length() / 2 - i) * 2偶数串的时候 ：   j =   i + (s.length() / 2 - i) * 2 - 1

所以结合以上规律即可构成出答案了。

这里也有个小细节，就是我们只需要遍历回文串的一半即可。

否则会将奇数串中的对称点也作为第二个不同的字符。

代码详解如下：

#include <iostream>
#include <cstring>
using namespace std;// 用于存储不同的字符
struct Char
{char now;int i;    // 当前下标 iint j;    // 对称下标 jinline Char():now('-'),i(-1),j(-1){}    // 默认构造函数
};
signed main()
{string s;getline(cin,s);int sz = s.size();    // 获取字符串长度if(sz <= 3){cout << -1 << endl; // 特判如果 小于等 3 那么一定是无解return 0;}Char a,b;    // 定义结构体用于存储两个不同的字符for(int i = 0;i < sz / 2;++i)    // 遍历对应回文串的一半即可{// 如果 a 还没存储好，我们现在给它存储if(a.now == '-'){a.now = s[i];a.i = i;// 存储对称下标 ja.j = (sz % 2 ? i + (sz / 2 - i) * 2 : i + (sz / 2 - i) * 2 - 1);    }else{if(b.now == '-' and s[i] != a.now)    // 出现不同 a 的字符{b.now = s[i];b.i = i;// 存储对称下标 jb.j = (sz % 2 ? i + (sz / 2 - i) * 2 : i + (sz / 2 - i) * 2 - 1);  break;    // 两个都存储完了推出循环}}}if(a.now == '-' || b.now == '-'){cout << -1 << endl;    // 如果没有第二个不同的字符，那么肯定无解return 0;}// 开始交换两个字符s[a.i] = s[a.j] = b.now;s[b.i] = s[b.j] = a.now;// 输出答案，即为使其中任意一个解cout << s << endl;return 0;
}