Longest Word In Dictionary Problem


Description

LeetCode Problem 720. Given a list of strings words representing an English dictionary, find 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. If there is no answer, return the empty string.

All the strings in the input will only contain lowercase letters.

Example:

1
2
3
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".


Solution

Brute Force Approach

A simple solution is to use the brute force approach.

We loop through every word in the dictionary. For each word, we loop through every prefix of the world and check whether that prefix of the word exists in the dictonary. Finally, we return the longest word that every prefix of the word exists in the dictionary.

The time complexity of this approach is O(n2m), where n is the length of the dictionary and m is the maximum length of the word in the dictionary. The space complexity is O(1).

Trie and Depth First Search Approach

We can use the data structure trie to store the dictionary and use depth first search to find the longest possible answer. Using the trie data structure can help us reduce the time complexity.

In every trie node, we use an array of length 26 to store possible next trie node, and a flag to indicate whether the trie node is the last letter of a word in the dictionary.

Suppose we have a dictionary of words like this, words = [“a”, “banana”, “app”, “appl”, “ap”, “apply”, “apple”, “bar”]. The trie structure we build looks like the following. If the node is an end of a word, there is a * next to it.

1
2
3
4
5
6
7
8
9
10
11
a*   b
|    |
p*   a
|    | \
p*   n  r*
|    |
l*   a
|    |
e*   n
     |
     a*

After we build the trie, we can use depth first search to find the longest word that every letter in that word is an end of a word (marked by * in the above) in the dictionary.

The time complexity can be reduced to O(sum(mi)), where mi is the length of a word in the dictionary. The space complexity is O(sum(mi)).


Sample C++ Code

This is a C++ implementation of the trie and depth first search approach.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct TrieNode {
    TrieNode* arr[26];
    bool is_end;
    TrieNode() {
        for (int i = 0; i < 26; i ++) arr[i] = NULL;
        is_end = false;
    }
};

void insert(TrieNode* root, string key) {
    TrieNode* curr = root;
    for (int i = 0; i < key.size(); i ++) {
        int idx = key[i] - 'a';
        if (curr->arr[idx] == NULL)
            curr->arr[idx] = new TrieNode();
        curr = curr->arr[idx];
    }
    curr->is_end = true;
}


void dfs(TrieNode* root, string key, string& ans) {
    if (root == NULL) return;
    for (int i = 0; i < 26; i ++) {
        if (root->arr[i] != NULL) {
            if (root->arr[i]->is_end == true) {
                key += (char)(i) + 'a';
                if (key.size() > ans.size())
                    ans = key;
                else if (key.size() == ans.size()) {
                    if (key < ans)
                        ans = key;
                }
                dfs(root->arr[i], key, ans);
                key.pop_back();
            }
        }
    }
}

string longestWord(vector<string>& words) {
    TrieNode* root = new TrieNode();
    for (int i = 0; i < words.size(); i ++)
        insert(root, words[i]);
    string ans;
    dfs(root, "", ans);
    return ans;
}

int main() {
    vector<string> words = {"w","wo","wor","worl", "world"};
    cout << longestWord(words) << endl;
}




Related Posts

Stream of Characters Problem

LeetCode 1032. Implement the StreamChecker class as follows. Constructor, initialize...

Maximum XOR of Two Numbers in an Array Problem

LeetCode 421. Given an integer array nums, return the maximum...

Implement Trie (Prefix Tree) Problem

LeetCode 208. Implement a Trie with insert, search, and startsWith...

Camelcase Matching Problem

LeetCode 1023. A query word matches a given pattern if...

Word Search II Problem

LeetCode 212. Given an m x n board of characters...

Replace Words Problem

LeetCode 648. Given a dictionary consisting of many roots, and...