Longest Word in Dictionary LeetCode solution in Python

1
# Runtime: 240 ms (Top 36.59%) | Memory: 15.2 MB (Top 46.59%)
2
class Solution:
3
    def longestWord(self, words: List[str]) -> str:
4
        TrieNode = lambda: defaultdict(TrieNode)
5
        root = TrieNode()
6
        for i, s in enumerate(words):
7
            cur = root
8
            for c in s:
9
                cur = cur[c]
10
            cur["$"] = i
11

12
        ans = ""
13
        st = list(root.values())
14
        while st:
15
            cur = st.pop()
16
            if "$" in cur:
17
                w = words[cur["$"]]
18
                if len(ans) < len(w) or len(ans) == len(w) and w < ans:
19
                    ans = w
20
                st.extend([cur[i] for i in cur if i != "$"])
21
        return ans