Solution: Word Formation Using a Hash Table
Let’s solve the Word Formation Using a Hash Table problem.
We'll cover the following
Statement
Given an array of words wordsArray
, determine whether a given target
can be formed by combining two words from the array in any order.
Constraints:
2
wordsArray.length
1
wordsArray[i].length
2
target.length
All words consist of lowercase English letters
Solution
In this solution, we aim to determine the possibility of forming a target word by combining two words from an array. Initially, we check all possible divisions of the target word into two parts. First, we insert all the words in the array into the hash table. Then, we iterate over each position in the target word, creating a prefix and a suffix. For each division, we check if the prefix and suffix exist in the hash table. If both are found in the hash table, we return TRUE, confirming that the target word can be formed. If no such combination is found in the hash table after checking all possible divisions, we return FALSE, indicating that the target word cannot be formed using two words from the given array.
Let’s look at the steps of the algorithm:
Create a hash table of all the words in the
wordsArray
.Start by iterating over the characters of the
target
to check all possible divisions.For each index
, divide the word into two parts: a prefix
and asuffix
.The
prefix
consists of the characters from indexto . The
suffix
consists of the characters from indexto the end of the word.
Check if the
prefix
andsuffix
exist in the hash table. This is done to see if each part of the divided word is present in the hash table or not.If the
prefix
andsuffix
are found in the hash table, return TRUE, indicating that the word can be formed by combining two words from the table.Otherwise, keep iterating to check other possible divisions.
If no such combination is found after iterating over the
target
to check all possible divisions, return FALSE, indicating that the word cannot be formed using two words from the hash table.
Let’s look at the illustration below to better understand the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.