# LeetCode 720: Longest Word in Dictionary

## Problem Restatement

We are given an array of strings:

```python
words
```

We need to find the longest word that can be built one character at a time by other words in the array.

A word is valid if every prefix formed by removing the last character also exists in the array.

For example:

```python
"world"
```

is valid only if all these words exist:

```python
"w"
"wo"
"wor"
"worl"
"world"
```

If there are multiple answers with the same length, return the lexicographically smallest one.

If no valid answer exists, return the empty string.

The official statement defines the valid word condition exactly this way and asks for the longest such word. ([leetcode.com](https://leetcode.com/problems/longest-word-in-dictionary/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array of strings `words` |
| Output | Longest buildable word |
| Valid condition | Every prefix must also exist |
| Tie rule | Return lexicographically smallest |
| No valid word | Return `""` |

The function shape is:

```python
class Solution:
    def longestWord(self, words: list[str]) -> str:
        ...
```

## Examples

Example 1:

```python
words = ["w","wo","wor","worl","world"]
```

The word:

```python
"world"
```

is valid because all prefixes exist.

Output:

```python
"world"
```

Example 2:

```python
words = ["a","banana","app","appl","ap","apply","apple"]
```

Both:

```python
"apple"
"apply"
```

are valid.

They have the same length.

Lexicographically:

```python
"apple" < "apply"
```

So the answer is:

```python
"apple"
```

## First Thought: Check Every Prefix

For every word:

1. Generate all prefixes.
2. Check whether each prefix exists in the dictionary.

For example:

```python
"apple"
```

requires checking:

```python
"a"
"ap"
"app"
"appl"
```

This works.

The main requirement is fast prefix lookup.

## Key Insight

Use a hash set for constant-time word lookup.

If we store all words in:

```python
word_set
```

then checking whether a prefix exists becomes:

```python
prefix in word_set
```

We can directly test every word.

While scanning:

- Prefer longer valid words.
- For equal lengths, prefer lexicographically smaller words.

## Algorithm

1. Convert `words` into a set.
2. Initialize:
   ```python
   answer = ""
   ```
3. For every word:
   - Check whether all prefixes exist.
   - If valid:
     - Update the answer if:
       - The word is longer, or
       - The same length but lexicographically smaller.
4. Return the answer.

To check validity:

For every prefix length from `1` to `len(word) - 1`:

```python
word[:i]
```

must exist in the set.

## Correctness

The algorithm checks every word in the input.

A word is accepted only if every shorter prefix exists in the set. Therefore every accepted word satisfies the required buildability condition.

If a word is missing even one prefix, the algorithm rejects it. Therefore no invalid word is accepted.

Among all valid words, the algorithm keeps the best candidate according to the problem rules. It replaces the current answer when it finds:

1. A longer valid word.
2. A lexicographically smaller valid word of the same length.

Thus after processing all words, the stored answer is exactly the longest valid word, with lexicographical tie-breaking handled correctly.

## Complexity

Let:

```python
n = number of words
m = maximum word length
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n * m^2)` | Each prefix slice may cost `O(m)` |
| Space | `O(nm)` | Store all words in the hash set |

The practical runtime is fast because word lengths are small in the problem constraints.

## Implementation

```python
class Solution:
    def longestWord(self, words: list[str]) -> str:
        word_set = set(words)
        answer = ""

        for word in words:
            valid = True

            for i in range(1, len(word)):
                if word[:i] not in word_set:
                    valid = False
                    break

            if valid:
                if (
                    len(word) > len(answer)
                    or (
                        len(word) == len(answer)
                        and word < answer
                    )
                ):
                    answer = word

        return answer
```

## Code Explanation

Store all words for fast lookup:

```python
word_set = set(words)
```

Track the current best answer:

```python
answer = ""
```

For each word, assume it is valid:

```python
valid = True
```

Then check all shorter prefixes:

```python
for i in range(1, len(word)):
```

If a prefix is missing:

```python
if word[:i] not in word_set:
```

the word cannot be built step by step:

```python
valid = False
break
```

If the word is valid, update the answer if it is better:

```python
if (
    len(word) > len(answer)
    or (
        len(word) == len(answer)
        and word < answer
    )
):
    answer = word
```

Finally:

```python
return answer
```

## Alternative: Sort and Build Incrementally

Another elegant approach:

1. Sort words lexicographically.
2. Maintain a set of buildable words.
3. A word is buildable if:
   - Its length is `1`, or
   - Its prefix without the last character is already buildable.

```python
class Solution:
    def longestWord(self, words: list[str]) -> str:
        words.sort()

        buildable = set()
        answer = ""

        for word in words:
            if len(word) == 1 or word[:-1] in buildable:
                buildable.add(word)

                if len(word) > len(answer):
                    answer = word

        return answer
```

This works because sorting lexicographically automatically handles tie-breaking.

## Alternative Complexity

| Metric | Value |
|---|---|
| Time | `O(n log n + nm)` |
| Space | `O(nm)` |

This version is often considered cleaner.

## Example Walkthrough

Use:

```python
words = ["a","banana","app","appl","ap","apply","apple"]
```

Check:

```python
"banana"
```

Missing prefixes:

```python
"b"
"ba"
...
```

So it is invalid.

Check:

```python
"apple"
```

Prefixes:

```python
"a"
"ap"
"app"
"appl"
```

All exist.

So `"apple"` is valid.

Check:

```python
"apply"
```

Prefixes:

```python
"a"
"ap"
"app"
"appl"
```

All exist.

Both `"apple"` and `"apply"` have length `5`.

Lexicographically:

```python
"apple" < "apply"
```

So the answer remains:

```python
"apple"
```

## Trie Perspective

This problem is also naturally solved with a trie.

In a trie:

- Each node represents a prefix.
- A word is valid only if every traversed node is marked as a complete word.

Trie solutions are useful when:

- Many prefix operations are needed.
- The dictionary is large.
- We want efficient incremental prefix traversal.

For this problem, the hash set solution is shorter and simpler.

## Testing

```python
def test_longest_word():
    s = Solution()

    assert s.longestWord(
        ["w","wo","wor","worl","world"]
    ) == "world"

    assert s.longestWord(
        ["a","banana","app","appl","ap","apply","apple"]
    ) == "apple"

    assert s.longestWord(
        ["b","br","bre","brea","break","breakf","breakfa"]
    ) == "breakfa"

    assert s.longestWord(
        ["a","b","ab","abc"]
    ) == "abc"

    assert s.longestWord(
        ["banana"]
    ) == ""

    assert s.longestWord(
        ["a","ar","art","arts","arty"]
    ) == "arts"

    print("all tests passed")

test_longest_word()
```

Test coverage:

| Test | Why |
|---|---|
| Standard chain | Confirms step-by-step buildability |
| Lexicographical tie | Confirms tie-breaking rule |
| Long valid chain | Confirms repeated prefix checking |
| Multiple starting letters | Confirms independent chains |
| No valid long word | Confirms empty result |
| Same-length candidates | Confirms smallest lexicographical answer |