How hard is LeetCode 720. Longest Word in Dictionary?

LeetCode 720. Longest Word in Dictionary is rated Medium on LeetCode.

What is the time complexity of LeetCode 720. Longest Word in Dictionary?

The Python solution on this page runs in O(L).

What is the space complexity of LeetCode 720. Longest Word in Dictionary?

The Python solution on this page uses O(L), where L is the sum of the lengths of all words auxiliary space.

What topics does LeetCode 720. Longest Word in Dictionary cover?

LeetCode 720. Longest Word in Dictionary is tagged Trie, Array, Hash Table, String and Sorting on LeetCode.

Longest Word in Dictionary — LeetCode 720 Python Solution

MediumTrieArrayHash TableStringSorting

Problem: #720
Pattern: Trie
Reading time: 7 min
Source: leetcode.com

The problem

Given an array of strings words representing an English Dictionary, return the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order.

Example

Input: words = ["w","wo","wor","worl","world"]
Output: "world"
Explanation: The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

Python solution

Python

class Trie:
    def __init__(self):
        self.children: List[Optional[Trie]] = [None] * 26
        self.is_end = False

    def insert(self, w: str):
        node = self
        for c in w:
            idx = ord(c) - ord("a")
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.is_end = True

    def search(self, w: str) -> bool:
        node = self
        for c in w:
            idx = ord(c) - ord("a")
            if node.children[idx] is None:
                return False
            node = node.children[idx]
            if not node.is_end:
                return False
        return True


class Solution:
    def longestWord(self, words: List[str]) -> str:
        trie = Trie()
        for w in words:
            trie.insert(w)
        ans = ""
        for w in words:
            if trie.search(w) and (
                len(ans) < len(w) or (len(ans) == len(w) and ans > w)
            ):
                ans = w
        return ans

Complexity

Measure	Complexity
Time	O(L)
Space	O(L), where L is the sum of the lengths of all words auxiliary

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 720. Longest Word in Dictionary is filed here because LeetCode tags it Trie, which is the vocabulary this hub collects.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 720. Longest Word in Dictionary?: LeetCode 720. Longest Word in Dictionary is rated Medium on LeetCode.
What is the time complexity of LeetCode 720. Longest Word in Dictionary?: The Python solution on this page runs in O(L).
What is the space complexity of LeetCode 720. Longest Word in Dictionary?: The Python solution on this page uses O(L), where L is the sum of the lengths of all words auxiliary space.
What topics does LeetCode 720. Longest Word in Dictionary cover?: LeetCode 720. Longest Word in Dictionary is tagged Trie, Array, Hash Table, String and Sorting on LeetCode.