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

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:

1. Input Parsing: Start with the given word and dictionary.
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 Counter

def 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.