Solution: Word Formation Using a Hash Table

Statement

Given a list of words words_list, determine whether a given target can be formed by combining two words from the list in any order.

Constraints:

• 2 $\leq$ words_list.length $\leq 10^3$

• 1 $\leq$ words_list[i].length $\leq 20$

• 2 $\leq$ target.length $\leq 40$

• 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 a list. Initially, we check all possible divisions of the target word into two parts. First, we insert all the words in the list 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 list.

Let’s look at the steps of the algorithm:

• Create a hash table of all the words in the words_list.

• Start by iterating over the characters of the target to check all possible divisions.

• For each index $i$, divide the word into two parts: a prefix and a suffix.

  • The prefix consists of the characters from index $0$ to $i-1$.

  • The suffix consists of the characters from index $i$ to the end of the word.

• Check if the prefix and suffix 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 and suffix 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: