Imprimir todas las particiones palindrómicas de una string

Dada una string s, particione s tal que cada string de la partición sea un palíndromo. Devolver todas las posibles particiones palíndromo de s. 

Ejemplo : 

Input  : s = "bcc"
Output : [["b", "c", "c"], ["b", "cc"]]

Input  : s = "geeks"
Output : [["g", "e", "e", "k", "s"], 
          ["g", "ee", "k", "s"]]

Tenemos que enumerar todas las particiones posibles para pensar en la dirección de la recursividad. Cuando estamos en el índice i, comprobamos de forma incremental que todas las substrings a partir de i sean palindrómicas. Si se encuentra, resolvemos recursivamente el problema para la string restante y lo agregamos a nuestra solución. 

La siguiente es la solución-

1. Mantendremos un vector bidimensional para almacenar todas las particiones posibles y un vector temporal para almacenar la partición actual, un nuevo índice inicial de string para verificar las particiones, ya que ya hemos verificado las particiones antes de este índice.
2. Ahora siga iterando más en la string y verifique si es palíndromo o no.
3. Si es un palíndromo, agregue esta string en el vector de particiones actual. Recurse en esta nueva string si no es el final de la string. Después de regresar, cambie el vector de partición actual al anterior, ya que podría haber cambiado en el paso recursivo.
4. Si llegamos al final de la string mientras iteramos, tenemos nuestras particiones en nuestro vector temporal, por lo que lo agregaremos en los resultados.

Para verificar si es un palíndromo o no, itere en la string tomando dos punteros. Inicialice el primero para comenzar y el otro para el final de la string. Si ambos caracteres son iguales, aumente el primero y disminuya el último puntero y siga iterando hasta que el primero sea menor que el último. 

Implementación:

// C++ program to print all palindromic partitions
// of a given string.
#include <bits/stdc++.h>
using namespace std;
 
// Returns true if str is palindrome, else false
bool checkPalindrome(string str)
{
    int len = str.length();
    len--;
    for (int i=0; i<len; i++)
    {
        if (str[i] != str[len])
            return false;
        len--;
    }
    return true;
}
 
void printSolution(vector<vector<string> > partitions)
{
    for (int i = 0; i < partitions.size(); ++i)
    {
        for(int j = 0; j < partitions[i].size(); ++j)
            cout << partitions[i][j] << " ";
        cout << endl;
    }
    return;
}
 
// Goes through all indexes and recursively add remaining
// partitions if current string is palindrome.
void addStrings(vector<vector<string> > &v, string &s,
                vector<string> &temp, int index)
{
    int len = s.length();
    string str;
    vector<string> current = temp;
    if (index == 0)
        temp.clear();
    for (int i = index; i < len; ++i)
    {
        str = str + s[i];
        if (checkPalindrome(str))
        {
            temp.push_back(str);
            if (i+1 < len)
                addStrings(v,s,temp,i+1);
            else
                v.push_back(temp);
            temp = current;
        }
    }
    return;
}
 
// Generates all palindromic partitions of 's' and
// stores the result in 'v'.
void partition(string s, vector<vector<string> >&v)
{
    vector<string> temp;
    addStrings(v, s, temp, 0);
    printSolution(v);
    return;
}
 
// Driver code
int main()
{
    string s = "geeks";
    vector<vector<string> > partitions;
    partition(s, partitions);
    return 0;
}

// Java program to print all palindromic partitions
// of a given string.
import java.util.ArrayList;
public class GFG
{    
    // Returns true if str is palindrome, else false
    static boolean checkPalindrome(String str)
    {
        int len = str.length();
        len--;
        for (int i=0; i<len; i++)
        {
            if (str.charAt(i) != str.charAt(len))
                return false;
            len--;
        }
        return true;
    }
     
    // Prints the partition list
    static void printSolution(ArrayList<ArrayList<String>>
                                          partitions)
    {
        for(ArrayList<String> i: partitions)
        {
            for(String j: i)
            {
                System.out.print(j+" ");
            }
            System.out.println();
        }
    }
      
    // Goes through all indexes and recursively add remaining
    // partitions if current string is palindrome.
    static ArrayList<ArrayList<String>> addStrings(ArrayList<
       ArrayList<String>> v, String s, ArrayList<String> temp,
                                             int index)
    {
        int len = s.length();
        String str = "";
        ArrayList<String> current = new ArrayList<>(temp);
         
        if (index == 0)
            temp.clear();
         
        // Iterate over the string
        for (int i = index; i < len; ++i)
        {
            str = str + s.charAt(i);
             
            // check whether the substring is
            // palindromic or not
            if (checkPalindrome(str))
            {
                // if palindrome add it to temp list
                temp.add(str);
                 
                if (i + 1 < len)
                {   
                    // recurr to get all the palindromic
                    // partitions for the substrings
                    v = addStrings(v,s,temp,i+1);
                }
                else
                {
                    // if end of the string is reached
                    // add temp to v
                    v.add(temp);
                }
                 
                // temp is reinitialize with the
                // current i.
                temp = new ArrayList<>(current);
            }
        }
        return v;
    }
      
    // Generates all palindromic partitions of 's' and
    // stores the result in 'v'.
    static void partition(String s, ArrayList<ArrayList<
                                          String>> v)
    {
        // temporary ArrayList to store each
        // palindromic string
        ArrayList<String> temp = new ArrayList<>();
         
        // calling addString method it adds all 
        // the palindromic partitions to v
        v = addStrings(v, s, temp, 0);
         
        // printing the solution
        printSolution(v);
    }
      
    // Driver code
    public static void main(String args[])
    {
        String s = "geeks";
        ArrayList<ArrayList<String>> partitions = new
                                           ArrayList<>();
        partition(s, partitions);
    }
}
// This code is contributed by Sumit Ghosh

# Python3 program to print all palindromic
# partitions of a given string.
def checkPalindrome(string):
     
    # Returns true if str is palindrome,
    # else false
    length = len(string)
    length -= 1
    for i in range(length):
        if string[i] != string[length]:
            return False
        length -= 1
    return True
 
def printSolution(partitions):
    for i in range(len(partitions)):
        for j in range(len(partitions[i])):
            print(partitions[i][j], end = " ")
        print()
 
def addStrings(v, s, temp, index):
     
    # Goes through all indexes and
    # recursively add remaining partitions
    # if current string is palindrome.
    length = len(s)
    string = ""
 
    current = temp[:]
 
    if index == 0:
        temp = []
    for i in range(index, length):
        string += s[i]
        if checkPalindrome(string):
            temp.append(string)
            if i + 1 < length:
                addStrings(v, s, temp[:], i + 1)
            else:
                v.append(temp)
            temp = current
 
def partition(s, v):
     
    # Generates all palindromic partitions
    # of 's' and stores the result in 'v'.
    temp = []
    addStrings(v, s, temp[:], 0)
    printSolution(v)
 
# Driver Code
if __name__ == "__main__":
    s = "geeks"
    partitions = []
    partition(s, partitions)
 
# This code is contributed by
# vibhu4agarwal

// C# program to print all palindromic partitions
// of a given string.
using System;
using System.Collections.Generic;
 
class GFG
{    
    // Returns true if str is palindrome, else false
    static bool checkPalindrome(String str)
    {
        int len = str.Length;
        len--;
        for (int i = 0; i < len; i++)
        {
            if (str[i] != str[len])
                return false;
            len--;
        }
        return true;
    }
     
    // Prints the partition list
    static void printSolution(List<List<String>>
                                        partitions)
    {
        foreach(List<String> i in partitions)
        {
            foreach(String j in i)
            {
                Console.Write(j+" ");
            }
            Console.WriteLine();
        }
    }
     
    // Goes through all indexes and recursively add remaining
    // partitions if current string is palindrome.
    static List<List<String>> addStrings(List<
    List<String>> v, String s, List<String> temp,
                                            int index)
    {
        int len = s.Length;
        String str = "";
        List<String> current = new List<String>(temp);
         
        if (index == 0)
            temp.Clear();
         
        // Iterate over the string
        for (int i = index; i < len; ++i)
        {
            str = str + s[i];
             
            // check whether the substring is
            // palindromic or not
            if (checkPalindrome(str))
            {
                // if palindrome add it to temp list
                temp.Add(str);
                 
                if (i + 1 < len)
                {
                    // recurr to get all the palindromic
                    // partitions for the substrings
                    v = addStrings(v,s,temp,i+1);
                }
                else
                {
                    // if end of the string is reached
                    // add temp to v
                    v.Add(temp);
                }
                 
                // temp is reinitialize with the
                // current i.
                temp = new List<String>(current);
            }
        }
        return v;
    }
     
    // Generates all palindromic partitions of 's' and
    // stores the result in 'v'.
    static void partition(String s, List<List<
                                        String>> v)
    {
        // temporary List to store each
        // palindromic string
        List<String> temp = new List<String>();
         
        // calling addString method it adds all
        // the palindromic partitions to v
        v = addStrings(v, s, temp, 0);
         
        // printing the solution
        printSolution(v);
    }
     
    // Driver code
    public static void Main(String []args)
    {
        String s = "geeks";
        List<List<String>> partitions = new
                                        List<List<String>>();
        partition(s, partitions);
    }
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// JavaScript program to print all palindromic partitions
// of a given string.
 
// Returns true if str is palindrome, else false
function checkPalindrome(str)
{
    let len = str.length;
    len--;
    for (let i=0; i<len; i++)
    {
        if (str[i] != str[len])
            return false;
        len--;
    }
    return true;
}
 
function printSolution(partitions)
{
    for (let i = 0; i < partitions.length; ++i)
    {
        for(let j = 0; j < partitions[i].length; ++j)
            document.write(partitions[i][j]," ");
        document.write("</br>");
    }
    return;
}
 
// Goes through all indexes and recursively add remaining
// partitions if current string is palindrome.
function addStrings(v,s,temp,index)
{
    let len = s.length;
    let str = "";
    let current = temp.slice();
    if (index == 0)
        temp = [];
    for (let i = index; i < len; ++i)
    {
        str = str + s[i];
        if (checkPalindrome(str))
        {
            temp.push(str);
            if (i+1 < len)
                addStrings(v,s,temp,i+1);
            else
                v.push(temp);
            temp = current;
        }
    }
    return;
}
 
// Generates all palindromic partitions of 's' and
// stores the result in 'v'.
function partition(s,v)
{
    let temp = [];
    addStrings(v, s, temp, 0);
    printSolution(v);
}
 
// Driver code
 
let s = "geeks";
let partitions = [];
partition(s, partitions);
 
// This code is contributed by shinjanpatra
 
</script>

g e e k s 
g ee k s 

Complejidad temporal : O(n ² ) 
Espacio auxiliar : O(n)

Artículo relacionado: Programación dinámica | Conjunto 17 (partición de palíndromo) 

Este artículo es una contribución de Anshul Goyal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.