Dada una array de strings arr[] que contiene N palabras, la tarea es imprimir todas las strings palindrómicas posibles combinando dos strings cualesquiera de la array dada.
Ejemplos:
Entrada : arr[] = [“geekf”, “geeks”, “o”, “keeg”, “abc”, “ba”]
Salida : [“geekfkeeg”, “geekskeeg”, “abcba”] Explicación: Debajo de los pares forma la string palindrómica al combinar: 1. “geekf” + “keeg” = “geekfkeeg” 2. “geeks” + “keeg” = “geekskeeg” 3. “abc” + “ba” = “abcba”Entrada :arr[] = [“dcb”, “yz”, “xy”, “efg”, “yx”]
Salida : [“xyyx”, “yxxy”]
Explicación:
1. “xy” + “yz” = “xyyz”
2. “yx” + “xy” = “yxxy”
Enfoque ingenuo: el enfoque ingenuo es iterar todos los pares posibles en la array de strings dada y verificar si la concatenación de la string forma palindrómica o no. En caso afirmativo, imprima ese par y verifique los siguientes pares.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar utilizando Hashing . A continuación se muestran los pasos:
- Almacene todas las palabras en un mapa con palabras como claves e índices como valores.
- Para cada palabra (por ejemplo, str ) en arr[], divida la string en s1 y s2 de modo que s1 + s2 = str .
- Después del paso anterior surgen dos casos:
- Caso 1: si s1 es una string palindrómica y el reverso de s2 está presente en el mapa hash, entonces obtenemos el par requerido ( reverso de s2 + palabra actual ).
- Caso 2: si s2 es una string palindrómica y si s1 inversa está presente en el mapa hash, entonces obtenemos un par ( palabra actual + inversa de s1 ).
- Repita los pasos anteriores para todas las strings de la array.
A continuación se muestra la implementación del enfoque anterior:
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;
}
Java
// Java program for the above approach
import java.util.*;
public class Main
{
// Function to check whether the string
// word is palindrome or not
static boolean ispalin(String word)
{
if (word.length() == 1
|| word.length() == 0) {
return true;
}
int l = 0;
int r = word.length() - 1;
// Iterate word
while (l <= r) {
if (word.charAt(l) != word.charAt(r)) {
return false;
}
l++;
r--;
}
return true;
}
// Function to find the palindromicPairs
static Vector<String> palindromicPairs(String[] words)
{
Vector<String> output = new Vector<String>();
if (words.length == 0 ||
words.length == 1)
{
return output;
}
// Insert all the strings with
// their indices in the hash map
HashMap<String, Integer> mp = new HashMap<>();
for (int i = 0; i < words.length; i++) {
mp.put(words[i], i);
}
// Iterate over all the words
for(int i = 0; i < words.length; 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]).length() == 0)
{
for(Map.Entry<String, Integer> key : mp.entrySet())
{
if (key.getValue() == i)
{
continue;
}
if (ispalin(key.getKey()))
{
output.add(key.getKey());
}
}
}
// Create all possible substrings
// s1 and s2
for(int j = 0; j < words[i].length(); j++)
{
String s1 = words[i].substring(0, j + 1);
String s2 = words[i].substring(j + 1);
// Case 1
// If s1 is palindrome and
// reverse of s2 is
// present in hashmap at
// index other than i
if (ispalin(s1))
{
StringBuffer arr = new StringBuffer(s2);
arr.reverse();
s2 = new String(arr);
String temp = s2;
if (mp.containsKey(s2) && mp.get(s2) != i)
{
String ans = s2 + words[i];
output.add(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;
StringBuffer arr = new StringBuffer(s1);
arr.reverse();
s1 = new String(arr);
if (mp.containsKey(s1) && mp.get(s1) != i)
{
String ans = words[i] + s1;
output.add(ans);
}
s1 = temp;
}
}
}
// Return output
return output;
}
public static void main(String[] args) {
String[] words = { "geekf", "geeks", "or", "keeg", "abc", "ba" };
// Function call
Vector<String> result = palindromicPairs(words);
// Print the palindromic strings
// after combining them
for(String x : result)
System.out.println(x);
}
}
// This code is contributed by mukesh07.
Python3
# Python3 program for the above approach
# Function to check whether the string
# word is palindrome or not
def ispalin(word):
if (len(word) == 1 or len(word)):
return True
l = 0
r = len(word) - 1
# Iterate word
while (l <= r):
if (word[l] != word[r]):
return False
l+= 1
r-= 1
return True
# Function to find the palindromicPairs
def palindromicPairs(words):
output = []
if (len(words) == 0 or len(words) == 1):
return output
# Insert all the strings with
# their indices in the hash map
mp = {}
for i in range(len(words)):
mp[words[i]] = i
# Iterate over all the words
for i in range(len( words)):
# 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 (len(words[i]) == 0):
for x in mp:
if (mp[x] == i):
continue
if (ispalin(x)):
output.append(x)
# Create all possible substrings
# s1 and s2
for j in range (len(words[i])):
s1 = words[i][0 : j + 1]
s2 = words[i][j + 1 : ]
# Case 1
# If s1 is palindrome and
# reverse of s2 is
# present in hashmap at
# index other than i
if (ispalin(s1)):
p = list(s2)
p.reverse()
s2 = ''.join(p)
temp = s2;
if (s2 in mp and mp[s2] != i):
ans = s2 + words[i]
output.append(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)):
temp = s1
p = list(s1)
p.reverse()
s1 = ''.join(p)
if (s1 in mp and mp[s1] != i):
ans = words[i] + s1
output.append(ans)
s1 = temp
# Return output
return output
# Driver Code
if __name__ == "__main__":
# Given array of words
words = [ "geekf", "geeks", "or",
"keeg", "abc", "ba" ]
# Function call
result = palindromicPairs(words);
# Print the palindromic strings
# after combining them
for x in result:
print(x)
# This code is contributed by chitranayal
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to check whether the string
// word is palindrome or not
static bool ispalin(string word)
{
if (word.Length == 1
|| word.Length == 0) {
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
static List<string> palindromicPairs(string[] words)
{
List<string> output = new List<string>();
if (words.Length == 0 ||
words.Length == 1)
{
return output;
}
// Insert all the strings with
// their indices in the hash map
Dictionary<string, int> mp = new Dictionary<string, int>();
for (int i = 0; i < words.Length; i++) {
mp[words[i]] = i;
}
// Iterate over all the words
for(int i = 0; i < words.Length; 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].Length == 0)
{
foreach(KeyValuePair<string, int> key in mp)
{
if (key.Value == i)
{
continue;
}
if (ispalin(key.Key))
{
output.Add(key.Key);
}
}
}
// Create all possible substrings
// s1 and s2
for(int j = 0; j < words[i].Length; j++)
{
string s1 = words[i].Substring(0, j + 1);
string s2 = words[i].Substring(j + 1);
// Case 1
// If s1 is palindrome and
// reverse of s2 is
// present in hashmap at
// index other than i
if (ispalin(s1))
{
char[] arr = s2.ToCharArray();
Array.Reverse(arr);
s2 = new string(arr);
string temp = s2;
if (mp.ContainsKey(s2) && mp[s2] != i)
{
string ans = s2 + words[i];
output.Add(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;
char[] arr = s1.ToCharArray();
Array.Reverse(arr);
s1 = new string(arr);
if (mp.ContainsKey(s1) && mp[s1] != i)
{
string ans = words[i] + s1;
output.Add(ans);
}
s1 = temp;
}
}
}
// Return output
return output;
}
static void Main()
{
string[] words = { "geekf", "geeks", "or", "keeg", "abc", "ba" };
// Function call
List<string> result = palindromicPairs(words);
// Print the palindromic strings
// after combining them
foreach(string x in result) {
Console.WriteLine(x);
}
}
}
// This code is contributed by rameshtravel07.
Javascript
<script>
// Javascript program for the above approach
// Function to check whether the string
// word is palindrome or not
function ispalin(word)
{
if (word.length == 1 ||
word.length == 0)
{
return true;
}
let l = 0;
let 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
function palindromicPairs(words)
{
let output = [];
if (words.length == 0 ||
words.length == 1)
{
return output;
}
// Insert all the strings with
// their indices in the hash map
let mp = new Map();
for(let i = 0; i < words.length; i++)
{
mp.set(words[i],i);
}
// Iterate over all the words
for(let i = 0; i < words.length; 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].length == 0)
{
for(let [key, value] of mp.entries())
{
if (value == i)
{
continue;
}
if (ispalin(key))
{
output.push(key);
}
}
}
// Create all possible substrings
// s1 and s2
for(let j = 0; j < words[i].length; j++)
{
let s1 = words[i].substring(0, j + 1);
let s2 = words[i].substring(j + 1);
// Case 1
// If s1 is palindrome and
// reverse of s2 is
// present in hashmap at
// index other than i
if (ispalin(s1))
{
s2 = s2.split("").reverse().join("");
let temp = s2;
if (mp.has(s2) && mp.get(s2) != i)
{
let ans = s2 + words[i];
output.push(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))
{
let temp = s1;
s1 = s1.split("").reverse().join("");
if (mp.has(s1) && mp.get(s1) != i)
{
let ans = words[i] + s1;
output.push(ans);
}
s1 = temp;
}
}
}
// Return output
return output;
}
// Driver Code
let words;
// Given array of words
words = [ "geekf", "geeks", "or",
"keeg", "abc", "ba" ];
// Function call
let result = palindromicPairs(words);
// Print the palindromic strings
// after combining them
for(let i = 0; i < result.length; i++)
{
document.write(result[i] + " <br>");
}
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
geekfkeeg geekskeeg abcba
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kritirikhi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA