Concatenated Words

To solve this coding challenge of finding all concatenated words in a given list, we'll first detail the approach and then provide precise pseudocode.

Explanation

The aim is to identify words in a list that are comprised entirely of at least two other words from the same list. To do this, we will use Depth-First Search (DFS) to check if a word can be broken down into smaller words that exist in the given list. Here's a detailed breakdown of the approach:

1. Set Creation : Convert the list of words into a set for O(1) time complexity look-up.
2. DFS Utility Function : A recursive function that checks if a given word can be split into smaller words that exist in the word set.
3. Main Logic :
1. Remove the current word from the set to avoid using the word itself during DFS.
2. Use DFS to check if the word can be formed by concatenating other words from the set.
3. If it can, add the word to the result list.
4. Add the word back to the set for subsequent operations.

Step-by-Step Explanation

4. Convert the list of words into a set for quick look-up.
5. Implement a DFS function that:
• Iterates through splits of the word.
• Checks if both the prefix and suffix of the split are in the set or can be broken down further.
6. In the main function, for each word:
• Temporarily remove the word from the set.
• Use the DFS function to determine if the word can be concatenated from other words in the set.
• If it is a concatenated word, store it in a result list.
• Add the word back to the set after the check.

Pseudocode with Comments

                                            
# Define function to find all concatenated words
function findAllConcatenatedWordsInADict(words):
# Helper function for Depth-First Search (DFS)
function dfs(word, wordSet):
# Loop through possible splits of the word
for i from 1 to length of word:
prefix = substring of word from start to i
suffix = substring of word from i to end
# Check if both parts are in word set
if prefix is in wordSet AND suffix is in wordSet:
return True
# Check recursively if prefix is in wordSet and suffix can be further split
if prefix is in wordSet AND dfs(suffix, wordSet):
return True
return False

# Convert list of words to a set for quick lookup
wordSet = convert words to set
result = empty list

# Iterate over each word in the list
for each word in words:
# Temporarily remove the word from the set
remove word from wordSet
# Check if the word can be formed by other words in the set
if dfs(word, wordSet):
add word to result
# Add the word back to the set
add word to wordSet

return result

                                        

Detailed Steps in Pseudocode

7. findAllConcatenatedWordsInADict Function :
* Convert the list of words into a set named
wordSet
for O(1) lookups. * Initialize an empty list
result
to store concatenated words.
8. DFS Helper Function :
* For a given word, iterate from index 1 to the length of the word. * Split the word into a
prefix
and
suffix
. * Check if both
prefix
and
suffix
are present in
wordSet
. * If either both parts are in the set or
prefix
is in the set and
suffix
can be broken down further by recursively calling
dfs
, return
True
. * If no valid split is found, return
False
.
9. Main Logic in findAllConcatenatedWordsInADict :
* For each word in the initial list:
* Temporarily remove the word from
wordSet
to avoid using it in the check. * Use the
dfs
function to determine if the word can be concatenated from other words. * If the word can be concatenated, add it to the
result
list. * Add the word back to
wordSet
after checking.
* Return the
result
list containing all the concatenated words found.

This detailed approach ensures that each word is checked efficiently, leveraging the power of recursion and set operations to determine if a word is a concatenated word.