educative.io

Educative

Alternate (better?) solution for Trie Word formation challenge

I think this is a better solution for this challenge since it can detect inputs which are combinations of more than two words, whereas the given solution using trie.search() can only detect two word combinations.

def is_formation_possible(dictionary, word):
    trie = Trie()
    for entry in dictionary:
        trie.insert(entry)

    def check_word(trie, word):
        current = trie.root
        found_till = 0
        for ind, letter in enumerate(word):
            index = trie.get_index(letter)
            # If letter is not found, then word not found
            if current.children[index] is None:
                break
            
            # If part word found, return rest of the word
            elif current.children[index].is_end_word:
                found_till = ind

            current = current.children[index]

        if max_found == 0:
            return False
        elif max_found == len(word)-1:
            return True
        else:
            return check_word(trie, word[max_found+1:])

    return check_word(trie, word)

Course: Educative: Interactive Courses for Software Developers
Lesson: Educative: Interactive Courses for Software Developers

Hello @atrocious_albatross
Thank you for sharing this code. But in this lesson we have to find whether a given word can be formed by combining two words from a dictionary.
Hope this answers your query

So, if the word can be formed using more than two words that’s not allowed as a solution?