打印所有可能的回文字符串，它由任意一对给定字符串生成
给定字符串字符串arr[]包含N个单词的数组，任务是通过组合给定数组中的任何两个字符串来打印所有可能的回文字符串。
示例：
输入：
arr[] = ["geekf", "geeks", "or", "keeg", "abc", "ba"]输出：
["geekfkeeg", "geekskeeg", "abcba"]解释：
以下对构成组合中的回文字符串：
"geekf" + "keeg" = "geekfkeeg""geeks" + "keeg" = "geekskeeg""abc" + "ba" = "abcba"输入：
arr[] = ["dcb", "yz", "xy", "efg", "yx"]输出：
["xyyx", "yxxy"]说明：
"xy"+"yz"="xyyz""yx"+"xy"="yxxy"
朴素的方法：朴素的方法是迭代给定字符串数组中的所有可能对，并检查字符串的连接是否生成回文。 如果是，则打印该对并检查下一对。
时间复杂度：O(N ^ 2)。
辅助空间：O(1)。
有效方法：可以使用哈希优化上述方法。 步骤如下：
-
将所有单词存储在映射中，其中单词作为键和索引作为值。
-
对于
arr[]中的每个单词（例如str），将字符串分成字符串s1和s2，这样s1 + s2 = str。 -
完成上述步骤后，出现两种情况：
-
情况 1：如果
s1是回文字符串，并且s2的反向出现在哈希映射中，则我们得到所需的对（反向的s2加当前单词的形式）。 -
情况 2：如果
s2是回文字符串，并且如果哈希映射中存在反向s1，那么我们得到一个对（当前单词加反向的s1）。
-
-
对数组中的所有字符串重复上述步骤。
下面是上述方法的实现：
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check whether the string
// word is palindrome or not
bool ispalin(string word)
{
if (word.length() == 1
|| word.empty()) {
return true;
}
int l = 0;
int r = word.length() - 1;
// Iterate word
while (l <= r) {
if (word[l] != word[r]) {
return false;
}
l++;
r--;
}
return true;
}
// Function to find the palindromicPairs
vector<string>
palindromicPairs(vector<string>& words)
{
vector<string> output;
if (words.size() == 0
|| words.size() == 1) {
return output;
}
// Insert all the strings with
// their indices in the hash map
unordered_map<string, int> mp;
for (int i = 0; i < words.size(); i++) {
mp[words[i]] = i;
}
// Iterate over all the words
for (int i = 0; i < words.size(); i++) {
// If the word is empty then
// we simply pair it will all the
// words which are palindrome
// present in the array
// except the word itself
if (words[i].empty()) {
for (auto x : mp) {
if (x.second == i) {
continue;
}
if (ispalin(x.first)) {
output.push_back(x.first);
}
}
}
// Create all possible substrings
// s1 and s2
for (int j = 0;
j < words[i].length(); j++) {
string s1 = words[i].substr(0, j + 1);
string s2 = words[i].substr(j + 1);
// Case 1
// If s1 is palindrome and
// reverse of s2 is
// present in hashmap at
// index other than i
if (ispalin(s1)) {
reverse(s2.begin(),
s2.end());
string temp = s2;
if (mp.count(s2) == 1
&& mp[s2] != i) {
string ans = s2 + words[i];
output.push_back(ans);
}
s2 = temp;
}
// Case 2
// If s2 is palindrome and
// reverse of s1 is
// present in hashmap
// at index other than i
if (ispalin(s2)) {
string temp = s1;
reverse(s1.begin(),
s1.end());
if (mp.count(s1) == 1
&& mp[s1] != i) {
string ans = words[i] + s1;
output.push_back(ans);
}
s1 = temp;
}
}
}
// Return output
return output;
}
// Driver Code
int main()
{
vector<string> words;
// Given array of words
words = { "geekf", "geeks", "or",
"keeg", "abc", "ba" };
// Function call
vector<string> result
= palindromicPairs(words);
// Print the palindromic strings
// after combining them
for (auto x : result) {
cout << x << endl;
}
return 0;
}
输出：
geekfkeeg
geekskeeg
abcba
时间复杂度：O(n)。
辅助空间：O(n)。
版权属于：月萌API www.moonapi.com，转载请注明出处
