# Given a dictionary of words and an input word, create a function that returns all valid step words.

By | August 29, 2024

A step word is formed by taking a given word, adding a letter, and anagramming the result. For example, starting with the word “APPLE”, you can add an “A” and anagram to get “APPEAL”. Given a dictionary of words and an input word, create a function that returns all valid step words.

To solve the problem of finding all valid step words from a given dictionary, you can break down the task into the following steps:

2. Generate Candidates: For each letter in the alphabet, add it to the given word at every possible position.
3. Anagram Check: After adding a letter, check if any of the generated words (anagrams) exist in the dictionary.
4. Return the Valid Words: Collect and return all valid step words.

Here’s a Python function that implements this logic:

`    from collections import Counterdef is_anagram(word1, word2):   return Counter(word1) == Counter(word2)def find_step_words(word, dictionary):    alphabet = 'abcdefghijklmnopqrstuvwxyz'    valid_step_words = []    # Generate all possible step words by adding one letter at each position    for letter in alphabet:        for i in range(len(word) + 1):            # Add the letter to the word            new_word = word[:i] + letter + word[i:]            # Check if the new word is in the dictionary and is an anagram            if new_word in dictionary and is_anagram(new_word, word + letter):                valid_step_words.append(new_word)    return valid_step_words# Example usage:word = "apple"dictionary = {"appeal", "apples", "maple", "paple", "apleap", "appealing"}result = find_step_words(word, dictionary)print(result)  # Output: ['appeal']`

### Explanation:

1. `is_anagram` Function:
• This function checks if two words are anagrams by comparing their letter counts using Python’s `Counter`.
2. `find_step_words` Function:
• Alphabet Loop: Iterates over each letter in the alphabet.
• Insertion Loop: For each letter, it inserts the letter at every possible position in the given word.
• Validation: After forming a new word, it checks if this word exists in the dictionary and if it’s a valid anagram of the original word plus the new letter.
• Result Collection: If both checks pass, the word is added to the list of valid step words.

### Example:

Given the word `"apple"` and the dictionary `{"appeal", "apples", "maple", "paple", "apleap", "appealing"}`, the function will return `['appeal']` as the only valid step word, since `"appeal"` can be formed by adding an “A” to `"apple"` and rearranging the letters.

### Complexity:

• Time Complexity: The function iterates over each letter in the alphabet (26 letters) and each possible position in the word (length + 1). For each generated word, it checks if it’s in the dictionary and if it’s an anagram. The time complexity is roughly O(26 * (n+1) * m), where n is the length of the word and m is the size of the dictionary.
• Space Complexity: The space complexity is O(m), where m is the size of the dictionary.

This function effectively finds all valid step words given a dictionary and a starting word.