打印所有可能的回文字符串,它由任意一对给定字符串生成

原文:https://www.geeksforgeeks.org/print-all-possible-palindromic-string-formed-using-any-pair-of-given-strings/

给定字符串字符串arr[]包含N个单词的数组,任务是通过组合给定数组中的任何两个字符串来打印所有可能的回文字符串。

示例

输入arr[] = ["geekf", "geeks", "or", "keeg", "abc", "ba"]

输出["geekfkeeg", "geekskeeg", "abcba"]

解释

以下对构成组合中的回文字符串:

  1. "geekf" + "keeg" = "geekfkeeg"
  2. "geeks" + "keeg" = "geekskeeg"
  3. "abc" + "ba" = "abcba"

输入arr[] = ["dcb", "yz", "xy", "efg", "yx"]

输出["xyyx", "yxxy"]

说明

  1. "xy"+"yz"="xyyz"
  2. "yx"+"xy"="yxxy"

朴素的方法:朴素的方法是迭代给定字符串数组中的所有可能对,并检查字符串的连接是否生成回文。 如果是,则打印该对并检查下一对。

时间复杂度O(N ^ 2)

辅助空间O(1)

有效方法:可以使用哈希优化上述方法。 步骤如下:

  1. 将所有单词存储在映射中,其中单词作为索引作为

  2. 对于arr[]中的每个单词(例如str),将字符串分成字符串s1s2,这样s1 + s2 = str

  3. 完成上述步骤后,出现两种情况:

    • 情况 1:如果s1是回文字符串,并且s2的反向出现在哈希映射中,则我们得到所需的对(反向的s2当前单词的形式)。

    • 情况 2:如果s2是回文字符串,并且如果哈希映射中存在反向s1,那么我们得到一个对(当前单词加反向的s1)。

  4. 对数组中的所有字符串重复上述步骤。

下面是上述方法的实现:

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)