通过交换相邻字符串的字符使所有字符串成为回文字符串
在本题中，我们将通过交换相邻字符串的字符，使给定数组的所有字符串成为回文字符串。
为了解决这个问题，我们将尝试使所有字符串中第 p 个字符和 str_len - p - 1 索引处的字符相同，并且只有当第 p 个索引处和 (str_len - p - 1) 索引处的所有字符相同时才有可能。
问题描述 - 我们给出了一个数组，其中包含多个长度为 N 的字符串。我们需要计算使数组中的所有字符串成为回文字符串所需的最少操作次数。我们可以在一次操作中交换任意两个相邻字符串的第 p 个字符。如果无法使所有字符串都成为回文字符串，则打印 -1。
示例
输入
arr = {"57", "65", "76"};
输出
2
说明
我们需要交换 '13' 和 '21' 的第二个字符。因此，字符串将变为 {"55", "67", "76"}。
接下来，交换第二个和第三个字符串的第一个字符。因此，最终的字符串将是 {'55', '77', '66'}。
所有最终字符串都是回文字符串。
输入
arr = {"aba", "ppp", "sss"}
输出
0
说明- 由于所有字符串都是回文字符串，因此我们无需执行任何操作。
输入
arr = {"nnn", "pqr", "rqt"}
输出
-1
解释- 无法通过交换相邻字符使所有字符串都成为回文字符串。
方法 1
要使任何字符串成为回文字符串，字符串的第 p 个索引和 (str_len - p - 1) 个索引处的字符必须相同。
这里，我们只能交换相邻字符串中相同索引处的字符。因此，我们可以从每个字符串中取出第 p 个字符并创建其列表。此外，我们还可以从 (str_len - p - 1) 个索引处取出字符串字符并创建列表。
之后，我们可以交换第二个列表中的相邻字符，以使两个列表相同。如果我们不能使任何列表相同，就无法使所有字符串都成为回文字符串。
例如，输入数组为 {"57", "65", "76"}。
因此，列表的 p = 0，str_len - p - 1 =1 的索引等于 {5, 6, 7} 和 {7, 5, 6}。
在这里，我们可以交换第二个列表的字符，使该列表等于第一个列表。
这样，我们需要计算从 0 到 len/2 的所有列表所需的移动次数，并将它们相加以获得最终输出。
算法
步骤 1 - 用 0 初始化 'cnt' 变量以存储最终结果。
步骤 2 - 开始遍历字符串从第 0 个到 len/2 索引。
步骤 3 - 通过执行 getColumnChars() 函数，在 temp1 列表中获取第 p 个索引的所有字符，并在 temp2 字符串中获取 (str_len - p -1) 索引的所有字符。
步骤 3.1 - 在 getColumnChars() 函数中，初始化 'chars' 列表。
步骤 3.2 - 遍历数组的所有字符串，从作为参数传递的索引处获取字符，并将其推送到 'chars' 列表。
步骤 3.3 - 返回 chars 列表。
步骤 4 - 如果 temp1 和 temp2 列表相同，则无需对当前列表执行任何操作。
步骤 5 - 现在，执行 isSwapPossible() 函数，检查是否可以通过交换字符使两个列表相同。
步骤 5.1 - 在 isSwapPossible() 函数中，定义 'freq' 映射来存储列表字符的频率。
步骤 5.2 - 遍历 temp1 列表，并将 freq 映射中 'ch' 键的值加 1。
步骤 5.3 - 遍历 temp2 列表，并将 freq 映射中 'ch' 键的值减 1。
步骤 5.4 - 遍历映射，如果任何键的值不为零，则返回 false，因为两个列表不包含相同的字符。
步骤 5.5 - 返回true。
步骤 6 - 如果 isSwapPossible() 函数返回 false，则将 cnt 更新为 -1，并跳出循环。
步骤 7 - 否则，执行 countSwaps() 函数，计算使两个列表相同所需的移动次数，方法是交换相邻字符，并将其返回值添加到 'cnt' 变量。
步骤 7.1 - 在 countSwaps() 函数中，将 'sps' 初始化为 0，然后开始遍历第一个列表。
步骤 7.2 - 如果两个列表中第 p 个索引处的字符不同，则执行以下步骤。否则，移至下一个索引。
步骤 7.3 - 如果 p 是最后一个索引，则交换 p - 1 和 p 索引处的字符。否则，交换 p 和 p + 1 索引处的字符。
步骤 7.4 - 将 'sps' 加 1，并将 p 重新初始化为 0。
步骤 7.5 - 返回 'sps' 值。
步骤 8 - 在主函数中返回 cnt 值。
示例
#include <bits/stdc++.h>
using namespace std;
// 从所有字符串的 ind 索引中获取字符
vector<char> getColumnChars(vector<string> arr, int ind) {
vector<char> chars;
for (auto it : arr) {
chars.push_back(it[ind]);
}
return chars;
}
bool isSwapPossible(vector<char> temp1, vector<char> temp2) {
map<char, int> freq;
// 存储 temp1 的字符频率
for (auto ch : temp1)
freq[ch]++;
// 减去 temp2 的字符频率
for (auto ch : temp2)
freq[ch]--;
for (auto ch : freq) {
// 当两行中的字符不相同时，返回 0。
if (ch.second != 0)
return 0;
}
return 1;
}
int countSwaps(vector<char> temp1, vector<char> temp2) {
int sps = 0;
int p = 0;
while (p != temp1.size()) {
if (temp1[p] != temp2[p]) {
if (p == temp1.size() - 1) {
// 对于最后一个字符
swap(temp2[p - 1], temp2[p]);
} else {
// 对于其他角色
swap(temp2[p], temp2[p + 1]);
}
// 增加交换次数
sps += 1;
p = 0;
}
else
p += 1;
}
return sps;
}
int numberOfSwaps(vector<string> arr) {
int cnt = 0;
int str_len = arr[0].size();
for (int p = 0; p < str_len / 2; p++) {
vector<char> temp1 = getColumnChars(arr, p);
vector<char> temp2 = getColumnChars(arr, str_len - p - 1);
// 当每个字符串在 p 和 str_len - p - 1 索引处包含相同的字符时
if (temp1 == temp2) {
continue;
}
// 检查是否可以通过交换字符使 temp1 和 temp2 相等
if (!isSwapPossible(temp1, temp2)) {
cnt = -1;
break;
} else {
cnt += countSwaps(temp1, temp2);
}
}
return cnt;
}
int main() {
vector<string> arr{"57", "65", "76"};
cout << "使所有字符串成为回文所需的最小交换次数是 " << numberOfSwaps(arr) << endl;
}
输出
使所有字符串成为回文所需的最小交换次数是 2
时间复杂度 - O(M*N*N)，其中 O(M) 用于遍历数组，O(N*N) 用于使所有字符串成为回文字符串。
空间复杂度 - O(N) 用于在映射中存储字符频率。
我们学习了如何计算使数组中所有字符串成为回文字符串所需的交换次数。逻辑部分是准备一个包含 p 个字符且 str_len - p - 1 个索引的列表，并使列表相同。
