极客笔记C++ 通过交换邻近字符串的字符，使所有字符串成为回文
在这个问题中，我们将通过交换相邻字符串的字符来使给定数组中的所有字符串成为回文。
为了解决这个问题，我们将尝试让所有字符串的第p个字符和第str_len – p – 1个字符相同，只有当整体的第p个字符和第(str_len – p – 1)个字符相同时，才有可能实现。
问题陈述 - 给定一个包含了N个长度相同的多个字符串的arr。我们需要计算使该数组中的所有字符串成为回文所需的最少操作次数。我们可以在一次操作中交换任意两个相邻字符串的第pth个字符。如果无法使所有字符串都成为回文，则打印-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 - 将’cnt’变量初始化为0，用于存储最终结果。
步骤2 - 从第0个到len/2个索引开始遍历字符串。
步骤3 - 通过执行getColumnChars()函数，从pth索引获取temp1列表中的所有字符，并从（str_len – p – 1）索引获取temp2字符串中的所有字符。
步骤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;
// Get character from the ind index of all strings
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;
// Store frequency of characters of temp1
for (auto ch : temp1)
freq[ch]++;
// Subtract frequency of characters of temp2
for (auto ch : temp2)
freq[ch]--;
for (auto ch : freq) {
// When characters are not the same in both rows, return 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) {
// For the last character
swap(temp2[p - 1], temp2[p]);
} else {
// For other characters
swap(temp2[p], temp2[p + 1]);
}
// Increment number of swaps
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);
// When each string contains the same character at p and str_len - p - 1 index
if (temp1 == temp2) {
continue;
}
// Check whether possible to make temp1 and temp2 equal by swapping characters
if (!isSwapPossible(temp1, temp2)) {
cnt = -1;
break;
} else {
cnt += countSwaps(temp1, temp2);
}
}
return cnt;
}
int main() {
vector<string> arr{"57", "65", "76"};
cout << "The minimum number of swaps required to make all strings palindromic is " << numberOfSwaps(arr) << endl;
}
输出
The minimum number of swaps required to make all strings palindromic is 2
时间复杂度 – O（MNN），其中O（M）用于遍历数组，而O（N*N）用于将所有字符串变为回文。
空间复杂度 – O（N）用于在映射中存储字符频率。
我们学会了计算使数组中所有字符串成为回文所需的交换次数。逻辑部分是准备一个包含p和str_len – p – 1索引的字符列表，并使列表相同。