Check if strings in a list can be formed by concatenation of elements in the same list

Question

Check if strings in a list can be formed by concatenation of elements in the same list

For example:

Input List -

{ best,  rockstar,   star,  guide,  bestguide, rock }

Output :-

rockstar -> rock, star

bestguide -> best, guide

Here "rockstar" can be formed using rock and star. Similarly "bestguide" can be formed by joining "best" and "guide".

Solution so far I have- Create all the combinations of string by joining each other(2 string together, 3 string together and so on) and store in a Map.

map structure could be as following

Map<String, List<String>>

{rockstar : [rock, star], ....}

Now check just traverse original list and check in the map. If it's found then it's one of possible solution.

Looking for a better solution with better time/space complexity

Answer 1

I think one standard approach would probably be to construct a trie from the dictionary. Then for each candidate, walk the trie and when a matching path reaches the end (marking a smaller word), continue from the top of the trie again with the remaining suffix of the candidate. We may need a few backtracking trials per candidate if similar matches exist; but in a dictionary of only 10,000, unless the data is degenerate, these should hopefully be few on average.

Answer 2

First, sorry for my bad English. I have a naive way, you should try it:

step 1: Sort the list in descending order of lengths of elements

step 2: In turn (from left to right of sorted list), add elements one by one to a tree under following rules:

• Each node of the tree contains a string, the root of the tree contains nothing

• String in each parent node contains strings in its child nodes.

• step 3: Get results: if length of string in a node equals sum of lengths of strings in child nodes then we get a desired result.

Answer 3

Here is the brute force approach. We can first form a list of the original terms, and then double-iterate that list to generate all combination possibilities. For each combination which is also already contained within the original list, we print that combination to the console.

String[] terms = new String[] { "best",  "rockstar",   "star",  "guide",  "bestguide", "rock" };
List<String> list = Arrays.asList(terms);
Set<String> set = new HashSet<String>(list);
for (int i=0; i < list.size()-1; ++i) {
    for (int j=i+1; j < list.size(); ++j) {
        if (set.contains(list.get(i) + list.get(j))) {
            System.out.println(list.get(i) + list.get(j) + " -> " + list.get(i) + ", " + list.get(j));
        }
        if (set.contains(list.get(j) + list.get(i))) {
            System.out.println(list.get(j) + list.get(i) + " -> " + list.get(j) + ", " + list.get(i));
        }
    }
}

This prints:

bestguide -> best, guide
rockstar -> rock, star