題目網址：https://leetcode.cn/problems/longest-word-in-dictionary/

題意：給一 string array words 組成的字典。返回 words 中最長的單字, 且該單字是由字典中其他單字逐步添加一個 char 而成的。

若其中有多個可行的答案, 則返回答案中順序最小的單字。若無答案, 則返回 empty string。

注意：words[i] 僅由小寫字母所組成。

Solution：

想法：利用 Sorting + Trie

  • 首先, 對 words 進行 sorting, 分成兩種情況:
    • string 越長的放越前面
    • 若兩 string 長度相同, 則將字母順序小的放前面
      e.g. "apple" 和 "apply"：兩者都有 "appl", 但是因為 "e" 在字母的順序中比 "y" 前面, 故 "apple" 應排在 "apply" 前面
  • 建立 Trie, 並將 words 中的每個單字 insert 到 Trie 中
  • 根據排序後的順序遍歷 words, 若 words[i] 中所有 prefix 都存在, 則直接返回 words[i]
class TrieNode {
public:
    TrieNode* children[26] = {nullptr};
    bool isEnd = false; // 預設每個 char 不為 end
};

class Trie {
public:
    Trie() : root(new TrieNode()) {}

    void insert(string& word){
        TrieNode *cur = root;

        for (const auto& c : word) {
            const int i = c - 'a';
            if (!cur->children[i]) {
                cur->children[i] = new TrieNode();
            }
            cur = cur->children[i];
        }

        cur->isEnd = true; // 將最後一個 char 設為 end
    }

    bool hasAllPrefix(string& word){
        TrieNode *cur = root;

        for (const auto& ch : word) {
            const int i = ch - 'a';

            // prefix 不存在 || prefix 存在, 但在 trie 中不為 end
            if (!cur->children[i] || !cur->children[i]->isEnd) {
                return false;
            }

            cur = cur->children[i];
        }

        return true;
    }

private:
    TrieNode *root;
};

class Solution {
public:
    string longestWord(vector<string>& words) {
        sort(words.begin(), words.end(), [](const string& s1, const string& s2){
            if (s1.size() != s2.size()) { // 長度不同時, 長度較長者放在前面
                return s1.size() > s2.size();
            }
            return s1 < s2; // 長度相同時, 字母順序較小者放在前面
        });

        Trie trie;
        for (const auto& word : words) {
            trie.insert(word);
        }

        for (const auto& word : words) {
            if (trie.hasAllPrefix(word)) {
                return word;
            }
        }

        return "";
    }
};

令總共有 n 個 word

  • time：$O(n \cdot log(n) + \displaystyle\sum_{i=1}^{n}w_i)$
    • $O(n \cdot log(n))$：sorting
    • $O(\displaystyle\sum_{i=1}^{n}w_i)$：
      • 每次插入 word[i] 需 $O(w_i)$, 其中 $w_i$ 為 word[i] 之長度
      • 每次查找 word[i] 其所有 prefix 需 $O(w_i)$, 其中 $w_i$ 為 word[i] 之長度
  • space：$O(26 \cdot \displaystyle\sum_{i=1}^{n}w_i)$ ➔ worse case：每個 word 的 prefix 皆不重覆
    • 總共 n 個 word, 每一個 word 有 $w_i$ 個 node, 而每個 node 又有 26 個 children