Stampa tutti i modi per rompere una stringa in forma di staffa
Dato una stringa, trova tutti i modi per rompere la stringa data in forma di staffa. Allegare ogni sottostringa all'interno di una parentesi.
Esempi:
Input : abc Output: (a)(b)(c) (a)(bc) (ab)(c) (abc) Input : abcd Output : (a)(b)(c)(d) (a)(b)(cd) (a)(bc)(d) (a)(bcd) (ab)(c)(d) (ab)(cd) (abc)(d) (abcd)
Ti consigliamo vivamente di ridurre al minimo il browser e provarlo da solo.
L'idea è quella di usare la ricorsione. Manteniamo due parametri: indice del carattere successivo da elaborare e finora la stringa di output. Iniziamo dall'indice del prossimo carattere da elaborare la sottostringa di appendici formata da una stringa non elaborata nella stringa di output e ricorrere alla stringa rimanente fino a quando non elaboremo l'intera stringa. Usiamo STD :: substr per formare la stringa di output. substr (pos n) restituisce una sottostringa di lunghezza n che inizia nella posizione POS della stringa corrente.
Il diagramma sotto mostra l'albero di ricorsione per la stringa di input 'ABC'. Ogni nodo sul diagramma mostra stringa elaborata (contrassegnata da verde) e stringa non trasformata (contrassegnata da rosso).
Di seguito è riportata l'implementazione dell'idea di cui sopra
C++ // C++ Program to find all combinations of Non- // overlapping substrings formed from given // string #include using namespace std ; // find all combinations of non-overlapping // substrings formed by input string str // index – index of the next character to // be processed // out - output string so far void findCombinations ( string str int index string out ) { if ( index == str . length ()) cout < < out < < endl ; for ( int i = index ; i < str . length (); i ++ ) { // append substring formed by str[index // i] to output string findCombinations ( str i + 1 out + '(' + str . substr ( index i + 1 - index ) + ')' ); } } // Driver Code int main () { // input string string str = 'abcd' ; findCombinations ( str 0 '' ); return 0 ; }
Java // Java program to find all combinations of Non- // overlapping substrings formed from given // string class GFG { // find all combinations of non-overlapping // substrings formed by input string str static void findCombinations ( String str int index String out ) { if ( index == str . length ()) System . out . println ( out ); for ( int i = index ; i < str . length (); i ++ ) // append substring formed by str[index // i] to output string findCombinations ( str i + 1 out + '(' + str . substring ( index i + 1 ) + ')' ); } // Driver Code public static void main ( String [] args ) { // input string String str = 'abcd' ; findCombinations ( str 0 '' ); } } // Contributed by Pramod Kumar
Python3 # Python3 Program to find all combinations of Non- # overlapping substrings formed from given # string # find all combinations of non-overlapping # substrings formed by input string str # index – index of the next character to # be processed # out - output string so far def findCombinations ( string index out ): if index == len ( string ): print ( out ) for i in range ( index len ( string ) 1 ): # append substring formed by str[index # i] to output string findCombinations ( string i + 1 out + '(' + string [ index : i + 1 ] + ')' ) # Driver Code if __name__ == '__main__' : # input string string = 'abcd' findCombinations ( string 0 '' ) # This code is contributed by # sanjeev2552
C# // C# program to find all combinations // of Non-overlapping substrings formed // from given string using System ; class GFG { // find all combinations of non-overlapping // substrings formed by input string str public static void findCombinations ( string str int index string @out ) { if ( index == str . Length ) { Console . WriteLine ( @out ); } for ( int i = index ; i < str . Length ; i ++ ) { // append substring formed by // str[index i] to output string findCombinations ( str i + 1 @out + '(' + str . Substring ( index ( i + 1 ) - index ) + ')' ); } } // Driver Code public static void Main ( string [] args ) { // input string string str = 'abcd' ; findCombinations ( str 0 '' ); } } // This code is contributed by Shrikant13
JavaScript // Javascript program for the above approach // find all combinations of non-overlapping // substrings formed by input string str // index – index of the next character to // be processed // out - output string so far function findCombinations ( string index out ) { if ( index == string . length ) { console . log ( out ); } for ( let i = index ; i < string . length ; i ++ ) { // append substring formed by str[index // i] to output string findCombinations ( string i + 1 out + '(' + string . substring ( index i + 1 ) + ')' ); } } // Driver Code const string = 'abcd' ; findCombinations ( string 0 '' ); // contributed by adityasharmadev01
Produzione
(a)(b)(c)(d) (a)(b)(cd) (a)(bc)(d) (a)(bcd) (ab)(c)(d) (ab)(cd) (abc)(d) (abcd)
Complessità temporale: O (n 2 )
Spazio ausiliario: O (n 2 )
