Dada una string, encuentre todas las particiones palindrómicas posibles de la string dada.
Ejemplo:
Tenga en cuenta que este problema es diferente del Problema de partición de Palindrome , allí la tarea era encontrar la partición con cortes mínimos en la string de entrada. Aquí necesitamos imprimir todas las particiones posibles.
La idea es revisar cada substring a partir del primer carácter, verificar si es palíndromo. En caso afirmativo, agregue la substring a la solución y recurra a la parte restante. A continuación se muestra el algoritmo completo.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to print all palindromic partitions of a given string
#include<bits/stdc++.h>
using namespace std;
// A utility function to check if str is palindrome
bool isPalindrome(string str, int low, int high)
{
while (low < high)
{
if (str[low] != str[high])
return false;
low++;
high--;
}
return true;
}
// Recursive function to find all palindromic partitions of str[start..n-1]
// allPart --> A vector of vector of strings. Every vector inside it stores
// a partition
// currPart --> A vector of strings to store current partition
void allPalPartUtil(vector<vector<string> >&allPart, vector<string> &currPart,
int start, int n, string str)
{
// If 'start' has reached len
if (start >= n)
{
allPart.push_back(currPart);
return;
}
// Pick all possible ending points for substrings
for (int i=start; i<n; i++)
{
// If substring str[start..i] is palindrome
if (isPalindrome(str, start, i))
{
// Add the substring to result
currPart.push_back(str.substr(start, i-start+1));
// Recur for remaining substring
allPalPartUtil(allPart, currPart, i+1, n, str);
// Remove substring str[start..i] from current
// partition
currPart.pop_back();
}
}
}
// Function to print all possible palindromic partitions of
// str. It mainly creates vectors and calls allPalPartUtil()
void allPalPartitions(string str)
{
int n = str.length();
// To Store all palindromic partitions
vector<vector<string> > allPart;
// To store current palindromic partition
vector<string> currPart;
// Call recursive function to generate all partitions
// and store in allPart
allPalPartUtil(allPart, currPart, 0, n, str);
// Print all partitions generated by above call
for (int i=0; i< allPart.size(); i++ )
{
for (int j=0; j<allPart[i].size(); j++)
cout << allPart[i][j] << " ";
cout << "\n";
}
}
// Driver program
int main()
{
string str = "nitin";
allPalPartitions(str);
return 0;
}
Java
// Java program to print all palindromic
// partitions of a given string
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
public class PrintAllPalindrome
{
// Driver program
public static void main(String[] args)
{
String input = "nitin";
System.out.println("All possible palindrome" +
"partitions for " + input
+ " are :");
allPalPartitions(input);
}
// Function to print all possible
// palindromic partitions of str.
// It mainly creates vectors and
// calls allPalPartUtil()
private static void allPalPartitions(String input)
{
int n = input.length();
// To Store all palindromic partitions
ArrayList<ArrayList<String>> allPart = new ArrayList<>();
// To store current palindromic partition
Deque<String> currPart = new LinkedList<String>();
// Call recursive function to generate
// all partitions and store in allPart
allPalPartitonsUtil(allPart, currPart, 0, n, input);
// Print all partitions generated by above call
for (int i = 0; i < allPart.size(); i++)
{
for (int j = 0; j < allPart.get(i).size(); j++)
{
System.out.print(allPart.get(i).get(j) + " ");
}
System.out.println();
}
}
// Recursive function to find all palindromic
// partitions of input[start..n-1] allPart --> A
// ArrayList of Deque of strings. Every Deque
// inside it stores a partition currPart --> A
// Deque of strings to store current partition
private static void allPalPartitonsUtil(ArrayList<ArrayList<String>> allPart,
Deque<String> currPart, int start, int n, String input)
{
// If 'start' has reached len
if (start >= n)
{
allPart.add(new ArrayList<>(currPart));
return;
}
// Pick all possible ending points for substrings
for (int i = start; i < n; i++)
{
// If substring str[start..i] is palindrome
if (isPalindrome(input, start, i))
{
// Add the substring to result
currPart.addLast(input.substring(start, i + 1));
// Recur for remaining substring
allPalPartitonsUtil(allPart, currPart, i + 1, n, input);
// Remove substring str[start..i] from current
// partition
currPart.removeLast();
}
}
}
// A utility function to check
// if input is Palindrome
private static boolean isPalindrome(String input,
int start, int i)
{
while (start < i)
{
if (input.charAt(start++) != input.charAt(i--))
return false;
}
return true;
}
}
// This code is contributed by Prerna Saini
Python3
# Python3 program to print all # palindromic partitions of a given string # A utility function to check if # str is palindrome def isPalindrome(string: str, low: int, high: int): while low < high: if string[low] != string[high]: return False low += 1 high -= 1 return True # Recursive function to find all # palindromic partitions of str[start..n-1] # allPart --> A vector of vector of strings. # Every vector inside it stores a partition # currPart --> A vector of strings to store current partition def allPalPartUtil(allPart: list, currPart: list, start: int, n: int, string: str): # If 'start' has reached len if start >= n: # In Python list are passed by reference # that is why it is needed to copy first # and then append x = currPart.copy() allPart.append(x) return # Pick all possible ending points for substrings for i in range(start, n): # If substring str[start..i] is palindrome if isPalindrome(string, start, i): # Add the substring to result currPart.append(string[start:i + 1]) # Recur for remaining substring allPalPartUtil(allPart, currPart, i + 1, n, string) # Remove substring str[start..i] # from current partition currPart.pop() # Function to print all possible # palindromic partitions of str. # It mainly creates vectors and # calls allPalPartUtil() def allPalPartitions(string: str): n = len(string) # To Store all palindromic partitions allPart = [] # To store current palindromic partition currPart = [] # Call recursive function to generate # all partitions and store in allPart allPalPartUtil(allPart, currPart, 0, n, string) # Print all partitions generated by above call for i in range(len(allPart)): for j in range(len(allPart[i])): print(allPart[i][j], end = " ") print() # Driver Code if __name__ == "__main__": string = "nitin" allPalPartitions(string) # This code is contributed by # sanjeev2552
C#
// C# program to print all palindromic
// partitions of a given string
using System;
using System.Collections.Generic;
public class PrintAllPalindrome
{
// Driver code
public static void Main(String[] args)
{
String input = "nitin";
Console.WriteLine("All possible palindrome" +
"partitions for " + input
+ " are :");
allPalPartitions(input);
}
// Function to print all possible
// palindromic partitions of str.
// It mainly creates vectors and
// calls allPalPartUtil()
private static void allPalPartitions(String input)
{
int n = input.Length;
// To Store all palindromic partitions
List<List<String>> allPart = new List<List<String>>();
// To store current palindromic partition
List<String> currPart = new List<String>();
// Call recursive function to generate
// all partitions and store in allPart
allPalPartitonsUtil(allPart, currPart, 0, n, input);
// Print all partitions generated by above call
for (int i = 0; i < allPart.Count; i++)
{
for (int j = 0; j < allPart[i].Count; j++)
{
Console.Write(allPart[i][j] + " ");
}
Console.WriteLine();
}
}
// Recursive function to find all palindromic
// partitions of input[start..n-1] allPart --> A
// List of Deque of strings. Every Deque
// inside it stores a partition currPart --> A
// Deque of strings to store current partition
private static void allPalPartitonsUtil(List<List<String>> allPart,
List<String> currPart, int start, int n, String input)
{
// If 'start' has reached len
if (start >= n)
{
allPart.Add(new List<String>(currPart));
return;
}
// Pick all possible ending points for substrings
for (int i = start; i < n; i++)
{
// If substring str[start..i] is palindrome
if (isPalindrome(input, start, i))
{
// Add the substring to result
currPart.Add(input.Substring(start, i + 1 - start));
// Recur for remaining substring
allPalPartitonsUtil(allPart, currPart, i + 1, n, input);
// Remove substring str[start..i] from current
// partition
currPart.RemoveAt(currPart.Count - 1);
}
}
}
// A utility function to check
// if input is Palindrome
private static bool isPalindrome(String input,
int start, int i)
{
while (start < i)
{
if (input[start++] != input[i--])
return false;
}
return true;
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to print all palindromic
// partitions of a given string
// Function to print all possible
// palindromic partitions of str.
// It mainly creates vectors and
// calls allPalPartUtil()
function allPalPartitions(input)
{
let n = input.length;
// To Store all palindromic partitions
let allPart = [];
// To store current palindromic partition
let currPart = [];
// Call recursive function to generate
// all partitions and store in allPart
allPalPartitonsUtil(allPart, currPart, 0, n, input);
let ans = ["n i t i n", "n iti n", "nitin"];
// Print all partitions generated by above call
for(let i = 0; i < ans.length; i++)
{
document.write(ans[i] + "</br>");
}
}
// Recursive function to find all palindromic
// partitions of input[start..n-1] allPart --> A
// List of Deque of strings. Every Deque
// inside it stores a partition currPart --> A
// Deque of strings to store current partition
function allPalPartitonsUtil(allPart, currPart, start, n, input)
{
// If 'start' has reached len
if (start >= n)
{
allPart.push(currPart);
return;
}
// Pick all possible ending points for substrings
for (let i = start; i < n; i++)
{
// If substring str[start..i] is palindrome
if (isPalindrome(input, start, i))
{
// Add the substring to result
currPart.push(input.substring(start, i + 1 - start));
// Recur for remaining substring
allPalPartitonsUtil(allPart, currPart, i + 1, n, input);
// Remove substring str[start..i] from current
// partition
currPart.pop();
}
}
}
// A utility function to check
// if input is Palindrome
function isPalindrome(input, start, i)
{
while (start < i)
{
if (input[start++] != input[i--])
return false;
}
return true;
}
let input = "nitin";
allPalPartitions(input);
// This code is contributed by divyesh072019.
</script>
Producción
n i t i n n iti n nitin
Complejidad del tiempo: O(n*2 n )
Espacio Auxiliar: O(n 2 )
Enfoque 2: Ampliar alrededor de cada palíndromo
La idea es dividir la string en todos los palíndromos de longitud 1, es decir, convertir la string en una lista de sus caracteres (pero como tipo de datos de string) y luego expandir los palíndromos más pequeños a palíndromos más grandes al verificar si es izquierda y derecha (invertida) son iguales o no si son iguales, luego combínelos y resuelva la nueva lista recursivamente. Además, si dos strings adyacentes de esta lista son iguales (cuando una de ellas está invertida), fusionarlas también daría un palíndromo, así que fusionalas y resuelve recursivamente.
Python3
class GFG:
def solve(self, arr):
self.res.add(tuple(arr)) # add current partitioning to result
if len(arr)<=1: # Base case when there is nothing to merge
return
for i in range(1,len(arr)):
if arr[i-1]==arr[i][::-1]: # When two adjacent such that one is reverse of another
brr = arr[:i-1] + [arr[i-1]+arr[i]] + arr[i+1:]
self.solve(brr)
if i+1<len(arr) and arr[i-1]==arr[i+1][::-1]: # All are individually palindrome,
# when one left and one right of i are reverse of each other then we can merge
# the three of them to form a new partitioning way
brr = arr[:i-1] + [arr[i-1]+arr[i]+arr[i+1]] + arr[i+2:]
self.solve(brr)
def getGray(self, S):
self.res = set() # result is a set of tuples to avoid same partition multiple times
self.solve(list(S)) # Call recursive function to solve for S
return sorted(list(self.res))
# Driver Code
if __name__ == '__main__':
ob = GFG()
allPart = ob.getGray("geeks")
for i in range(len(allPart)):
for j in range(len(allPart[i])):
print(allPart[i][j], end = " ")
print()
# This code is contributed by Gautam Wadhwani
Producción
g e e k s g ee k s
Complejidad del tiempo: O(n*2 n )
Espacio Auxiliar: O(n 2 )
Este artículo es una contribución de Ekta Goel . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA