Challenge: Word Formation from a Given Dictionary Using a Trie
If you are given a dictionary and a word, can you use a Trie to find if the given word can be formed by combining two dictionary words? A solution is placed in the "solution" section to help you, but we would suggest you should solve it on your own first.
We'll cover the following
Problem Statement
In this problem, you have to implement the isFormationPossible()
function to find whether or not the given word can be formed by combining two words from the dictionary.
Function Prototype:
boolean isFormationPossible(String[] dict, String word);
Here, dict is the dictionary containing unique strings, and word is a string.
Output:
It returns true
if the given word can be generated by combining two words from the given dictionary; otherwise, it returns false
.
Sample Input
String dict[] = {"the" ,"hello", "there", "answer", "any", "Dragon",
"world", "their", "inc"};
String word = "helloworld"
Sample Output
true
Explanation
helloworld
can be formed by combining hello
and world
from the “dictionary”, so the program returns true.
Here’s an illustration of the given challenge:
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.