Find the longest string that can be made up of other strings from the array | C ++ implementation of the approach ; Comparator to sort the string by their lengths in decreasing order ; Function that returns true if string s can be made up of by other two string from the array after concatenating one after another ; If current string has been processed before ; If current string is found in the map and it is not the string under consideration ; Split the string into two contiguous sub - strings ; If left sub - string is found in the map and the right sub - string can be made from the strings from the given array ; If everything failed , we return false ; Function to return the longest string that can made be made up from the other string of the given array ; Put all the strings in the map ; Sort the string in decreasing order of their lengths ; Starting from the longest string ; If current string can be made up from other strings ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool compare ( string s1 , string s2 ) { return s1 . size ( ) > s2 . size ( ) ; } bool canbuildword ( string & s , bool isoriginalword , map < string , bool > & mp ) { if ( mp . find ( s ) != mp . end ( ) && mp [ s ] == 0 ) return false ; if ( mp . find ( s ) != mp . end ( ) && mp [ s ] == 1 && isoriginalword == 0 ) { return true ; } for ( int i = 1 ; i < s . length ( ) ; i ++ ) { string left = s . substr ( 0 , i ) ; string right = s . substr ( i ) ; if ( mp . find ( left ) != mp . end ( ) && mp [ left ] == 1 && canbuildword ( right , 0 , mp ) ) { return true ; } } mp [ s ] = 0 ; return false ; } string printlongestword ( vector < string > listofwords ) { map < string , bool > mp ; for ( string s : listofwords ) { mp [ s ] = 1 ; } sort ( listofwords . begin ( ) , listofwords . end ( ) , compare ) ; for ( string s : listofwords ) { if ( canbuildword ( s , 1 , mp ) ) return s ; } return " - 1" ; } int main ( ) { vector < string > listofwords = { " geeks " , " for " , " geeksfor " , " geeksforgeeks " } ; cout << printlongestword ( listofwords ) ; return 0 ; }