Encuentre la string más larga que puede estar formada por otras strings de la array

Dada una array de strings arr[] , la tarea es encontrar la string más grande en la array que se compone de las otras strings de la array después de concatenar una tras otra. Si no existe tal string, imprima -1 .
Ejemplos: 
 

Entrada: arr[] = {“geeks”, “for”, “geeksfor”, “geeksforgeeks”} 
Salida: geeksforgeeks 
“geeksforgeeks” se compone de (“geeks” + “for” + “geeks”). 
Aunque «geeksfor» también se compone de otras strings 
, no es la string más grande.
Entrada: arr[] = {“Oye”, “tú”, “detente”, “derecha”, “allí”} 
Salida: -1 
 

Acercarse: 
 

1. Ordena todas las strings según su longitud en orden decreciente.
2. Ahora, a partir de la string más larga. Verifique todos los prefijos posibles de la string si está presente en la array dada y para la parte restante de la string, verifique recursivamente si se puede formar a partir de otras strings de la array.
3. El mapa se puede usar para verificar si existe una string en la array o no. La primera string que satisface las condiciones anteriores es la respuesta.
4. Si no existe tal string, imprima -1.

A continuación se muestra la implementación del enfoque anterior:
 

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

# Python implementation of the approach
 
# Function that returns true if string s can be
# made up of by other two string from the array
# after concatenating one after another
def canbuildword(s, isoriginalword, mp):
 
    # If current string has been processed before
    if s in mp and mp[s] == 0:
        return False
 
    # If current string is found in the map and
    # it is not the string under consideration
    if s in mp and mp[s] == 1 and isoriginalword == 0:
        return True
 
    for i in range(1, len(s)):
 
        # Split the string into two
        # contiguous sub-strings
        left = s[:i]
        right = s[i:]
 
        # 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 left in mp and mp[left] == 1 and canbuildword(right, 0, mp):
            return True
 
    # If everything failed, we return false
    mp[s] = 0
    return False
 
# Function to return the longest string
# that can made be made up from the
# other string of the given array
def printlongestword(listofwords):
 
    # Put all the strings in the map
    mp = dict()
    for i in listofwords:
        mp[i] = 1
 
    # Sort the string in decreasing
    # order of their lengths
    listofwords.sort(key=lambda x: len(x), reverse=True)
 
    # Starting from the longest string
    for i in listofwords:
 
        # If current string can be made
        # up from other strings
        if canbuildword(i, 1, mp):
            return i
 
    return "-1"
 
# Driver code
if __name__ == "__main__":
    listofwords = ["geeks", "for", "geeksfor",
                "geeksforgeeks"]
 
    print(printlongestword(listofwords))
 
# This code is contributed by
# sanjeev2552

<script>
 
// JavaScript implementation of the approach
 
// Comparator to sort the string by
// their lengths in decreasing order
function compare(s1, s2)
{
    return s2.length - s1.length;
}
 
// Function that returns true if string s can be
// made up of by other two string from the array
// after concatenating one after another
function canbuildword(s,isoriginalword,mp)
{
 
    // If current string has been processed before
    if (mp.has(s) && mp.get(s) == 0)
        return false;
 
    // If current string is found in the map and
    // it is not the string under consideration
    if (mp.has(s) && mp.get(s) == 1
        && isoriginalword == 0) {
        return true;
    }
 
    for (let i = 1; i < s.length; i++) {
 
        // Split the string into two
        // contiguous sub-strings
        let left = s.substring(0, i);
        let right = s.substring(i);
 
        // 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 (mp.has(left) == true && mp.get(left) == 1
            && canbuildword(right, 0, mp)) {
            return true;
        }
    }
 
    // If everything failed, we return false
    mp.set(s,0);
    return false;
}
 
// Function to return the longest string
// that can made be made up from the
// other string of the given array
function printlongestword(listofwords)
{
 
    // Put all the strings in the map
    let mp = new Map();
    for (let s of listofwords) {
        mp.set(s,1);
    }
 
    // Sort the string in decreasing
    // order of their lengths
    listofwords.sort(compare);
 
    // Starting from the longest string
    for (let s of listofwords) {
 
        // If current string can be made
        // up from other strings
        if (canbuildword(s, 1, mp))
            return s;
    }
 
    return "-1";
}
 
// Driver code
let listofwords = [ "geeks", "for", "geeksfor", "geeksforgeeks" ];
document.write(printlongestword(listofwords));
 
// This code is contributed by shinjanpatra
 
</script>

geeksforgeeks

Complejidad temporal: O(N^3)
Espacio auxiliar : O(N).