Word formation using concatenation of two dictionary words

Given a dictionary find out if given word can be made by two words in the dictionary. 
Note: Words in the dictionary must be unique and the word to be formed should not be a repetition of same words that are present in the Trie.

Examples: 

Input : dictionary[] = {"news", "abcd", "tree", 
                              "neveropen", "paper"}   
        word = "newspaper"
Output : Yes
We can form "newspaper" using "news" and "paper"

Input : dictionary[] = {"neveropen", "code", "xyz", 
                           "forneveropen", "paper"}   
        word = "neveropen"
Output : Yes

Input : dictionary[] = {"geek", "code", "xyz", 
                           "forneveropen", "paper"}   
        word = "neveropen"
Output : No

The idea is store all words of dictionary in a Trie. We do prefix search for given word. Once we find a prefix, we search for rest of the word.

Algorithm :  

1- Store all the words of the dictionary in a Trie.
2- Start searching for the given word in Trie.
   If it partially matched then split it into two
   parts and then search for the second part in
   the Trie.
3- If both found, then return true.
4- Otherwise return false.

Below is the implementation of above idea. 

Output: 

Yes

Exercise : 
A generalized version of the problem is to check if a given word can be formed using concatenation of 1 or more dictionary words. Write code for the generalized version.

Time Complexity: The time complexity of the given program is O(MN), where M is the length of the given word and N is the number of words in the dictionary. This is because the program needs to traverse the given word and perform a prefix search in the trie for each substring of the word, which takes O(M) time. Additionally, the program needs to insert all the words in the dictionary into the trie, which takes O(NM) time.

Auxiliary Space: The space complexity of the program is O(NM), where N is the number of words in the dictionary and M is the maximum length of a word in the dictionary. This is because the program needs to store the trie data structure, which requires O(NM) space.

Another Approach

The above approach is implementing the Trie data structure to efficiently store and search the dictionary words. However, we can optimize the code by using the unordered_set data structure instead of Trie. The unordered_set is a hash-based data structure that has an average constant time complexity O(1) for insertion and search operations. Therefore, it can be used to efficiently search for words in the dictionary.

Approach:

1. Check if the given word exists in the dictionary. If it does, return true.
2. If the given word is not found in the dictionary, then check if it can be formed by concatenating two or more words from the dictionary recursively.
3. To check if a word can be formed by concatenating two or more words from the dictionary, the code splits the word into a prefix and a suffix at every possible position and then checks if the prefix exists in the dictionary.
4. If the prefix exists in the dictionary, then the suffix is checked recursively to see if it can be formed by concatenating two or more words from the dictionary. This is done by calling the “isPossible” function recursively with the suffix and the dictionary as input.
5. If the suffix can be formed by concatenating two or more words from the dictionary, then the entire word can be formed by concatenating the prefix and suffix. In this case, the function returns true.
6. If none of the prefixes can be found in the dictionary, or if none of the suffixes can be formed by concatenating two or more words from the dictionary, then the function returns false.

Algorithm:

This code uses recursion to check whether a given word can be formed by concatenating two words from a given dictionary.

• The function “isPossible” takes two parameters: an unordered_set “dict” containing the dictionary of words and a string word to be checked.
• If the word is found in the dictionary, the function returns true. Otherwise, it recursively checks all possible prefixes and suffixes of the word to see if they can be formed by concatenating two words from the “dict”.
• The recursion stops when either the prefix is not found in the dictionary, or the suffix cannot be formed by concatenating two words from the “dict”.
• If the word can be formed by concatenating two words from the “dict”, the function returns true. Otherwise, it returns false.
• The “main” function creates an “unordered_set” of strings containing the dictionary, and then calls the “isPossible” function to check if the given word can be formed by concatenating two words from the dictionary. Finally, it prints “Yes” if the word can be formed, and “No” otherwise.

Below is the implementation of the above approach:

Output:

Yes

Time Complexity: The time complexity of the “isPossible” function in this code is O(N^3), where N is the length of the input word. This is because, in the worst case, the function will need to check every possible partition of the word into two parts, which is O(N^2), and for each partition, it may need to recursively check both parts, which can take an additional O(N) time.

Auxiliary Space: The space complexity of this function is also O(N^3) in the worst case, due to the recursion stack. Specifically, in the worst case, the recursion depth will be O(N), and at each level of the recursion, the function may need to store a string of length up to N. Therefore, the overall space complexity is O(N^3).

This article is contributed by Sahil Chhabra . If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.