Find the longest word in the array consisting of other words in the array

Question

I have an array of words and need to find the longest word in the array which consists of other words in this array. For example:

  String[] mass = {
            "five",
            "fivetwo",
            "fourfive",
            "fourfivetwo",
            "one",
            "onefiveone",
            "two",
            "twofivefourone"
        };

The result should be "fourfivetwo" -> "fourfive" "two". Can you please help me to find the algorithm?

Answer 1

Thank you all , I had already decided , if anyone is interested here's the code . I'm ashamed of it, but it works

public class MyMap {

private Map<String, ArrayList<Pair>> map = new TreeMap<String, ArrayList<Pair>>();
private String[] key;
// create special map
//key = element our array
//value = pair elemene 
//              string = word which contains in this key
//              int = count this word (which contains in this key)

public MyMap(String[] ArrayWord) {
    key = ArrayWord;
    //init arraylist
    for (int i = 0; i < ArrayWord.length; i++) {
        map.put(ArrayWord[i], new ArrayList<Pair>());
    }
    //find word which containing key
    /*
     example:
     String[] mass = {
     "f",
     "five",
     "fivetwo",
     "one",
     "onefiveone",
     "two"
     };
     map[0] => f->[]
     map[1] => five->[(f:1)]
     map[2] => fivetwo->[(f:1)(five:1)(two:1)]
     map[3] => one->[]
     map[4] => onefiveone->[(f:1)(five:1)(one:2)]
     map[5] => two->[]*/
    for (int i = 0; i < ArrayWord.length; i++) {
        for (int j = 0; j < ArrayWord.length; j++) {
            if (i != j) {
                int count = 0;
                if (ArrayWord[i].contains(ArrayWord[j])) {
                    String str = ArrayWord[i];
                    // find count word which contains in this key
                    while (str.contains(ArrayWord[j])) {
                        str = str.replaceFirst(ArrayWord[j], "-");
                        count++;
                    }
                    Pair help = new Pair(ArrayWord[j], count);
                    map.get(ArrayWord[i]).add(help);
                }

            }
        }
    }
}

public String getCompoundWord() {
    String word = "";
    //check have we compound word or not 
    if (isHaveCompoundWords()) {
        /*remove Unique Elements of the words are found*/
        deleteContainingWord();
        /* find index element*/
        int index = findIndexCompoundWord();
        //return -1 if we have no word which compound just with other words array
        try {
            word = key[findIndexCompoundWord()];
            return word;
        } catch (IndexOutOfBoundsException ex) {
            System.out.println("Have no word which compound just with other words array");
        }
    } else {
        return "Have no word which compound with other words array, just unique element";
    }

    return key[findIndexCompoundWord()];
}

private void deleteContainingWord() {
    /*
     update map
     after procedure we would have map like this           
     String[] mass = {
     "f",
     "five",
     "fivetwo",
     "one",
     "onefiveone",
     "two"
     };
     map[0] => f->[]
     map[1] => five->[(f:1)]
     map[2] => fivetwo->[(f:1)(ive:1)(two:1)]
     map[3] => one->[]
     map[4] => onefiveone->[(f:1)(ive:1)(one:2)]
     map[5] => two->[]
     */
    for (int i = 0; i < map.size(); i++) {
        if (map.get(key[i]).size() > 0) {
            ArrayList<Pair> tmp = map.get(key[i]);
            for (int j = tmp.size() - 1; j >= 0; j--) {
                for (int k = tmp.size() - 1; k >= 0; k--) {
                    if (k != j) {
                        // if word contains other word2, remove part word
                        if (tmp.get(j).getName().contains(tmp.get(k).getName())) {
                            String s = tmp.get(j).getName().replace(tmp.get(k).getName(), "");
                            tmp.get(j).setName(s);
                        }
                    }
                }
            }
            map.put(key[i], tmp);
        }
    }
}

private int findIndexCompoundWord() {
    int indexMaxCompaneWord = -1;
    int maxCompaneWordLenght = 0;
    for (int i = 0; i < map.size(); i++) {
        if (map.get(key[i]).size() > 0) {
            ArrayList<Pair> tmp = map.get(key[i]);
            int currentWordLenght = 0;
            for (int j = 0; j < tmp.size(); j++) {
                if (!tmp.get(j).getName().isEmpty()) {
                    currentWordLenght += tmp.get(j).getName().length() * tmp.get(j).getCount();
                }
            }
            if (currentWordLenght == key[i].length()) {
                if (maxCompaneWordLenght < currentWordLenght) {
                    maxCompaneWordLenght = currentWordLenght;
                    indexMaxCompaneWord = i;
                }
            }
        }
    }
    return indexMaxCompaneWord;
}

private boolean isHaveCompoundWords() {
    boolean isHaveCompoundWords = false;
    for (int i = 0; i < map.size(); i++) {
        if (map.get(key[i]).size() > 0) {
            isHaveCompoundWords = true;
            break;
        }
    }
    return isHaveCompoundWords;
}

}

Answer 2

There exists solution using string matching algorithm KMP and graphs.

Algorithm:

1) Iterate over words. Set each word for "main word", the word you want to build. Execute following steps for each such word.

2) You fixed one word, lets call it W. Now iterate over all words again and run KPM comparing them to W. Now you can build a graph on letters of word W. Lets explain on example:

W = "abacdeeee"
Other_word = ["aba", "cde", "eee"]

Word "aba" would connect letter 1 in word W to letter 4.
Word "cde" would connect 4 to 7.
Word "eee" would connect 7 to 9.

Each letter in W is node and other words will make edges. 
If there exists a path between first and last letter, which you can 
check using BFS/DFS, you can build word W out of other words.

3) Repeat the process for each word and choose the longest that can be built from others.

Time complexity:

Lets say N is number of words and L is average length.

For a single word you run KMP with each other word, which would take O(N * (L + L)). Building graph takes O(N^2) in worst case, same for BFS. For each word W you spend O(NL + N^2) worst case, but number of edges will most likely be proportional to N, so average is O(NL).

As you need to the above for each N, you get result:

Worst complexity: O(N^2*L + N^3)

Average complexity: O(N^2*L)