Problem statement

https://binarysearch.com/problems/Ghost/

Solution

First, we put all words to trie. Then we use game theory to solve it, using loosing and winning positions and dfs.

Complexity

It is O(n) for time and space, where n is total length of all words we have.

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end_node = 0

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        root = self.root
        for symbol in word:
            root = root.children.setdefault(symbol, TrieNode())
        root.end_node = 1

class Solution:
    def solve(self, words):
        trie = Trie()
        for word in words:
            trie.insert(word)

        def dfs(node):
            if node.end_node == 1: return True
            if any(not dfs(node.children[symbol]) for symbol in node.children): return True
            return False

        return dfs(trie.root)