【面試高頻題】難度 1/5，可用 Trie 進階的模拟題

題目描述

這是 LeetCode 上的 ​​720. 詞典中最長的單詞​​ ，難度為 簡單。

Tag : 「模拟」、「哈希表」、「字典樹」

給出一個字元串數組 ​

​words​

​​ 組成的一本英語詞典。傳回 ​

​words​

​​ 中最長的一個單詞，該單詞是由 ​

​words​

​ 詞典中其他單詞逐漸添加一個字母組成。

若其中有多個可行的答案，則傳回答案中字典序最小的單詞。若無答案，則傳回空字元串。

示例 1：

輸入：words = ["w","wo","wor","worl", "world"]

輸出："world"

解釋： 單詞"world"可由"w", "wo", "wor", 和 "worl"逐漸添加一個字母組成。      

示例 2：

輸入：words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]

輸出："apple"

解釋："apply" 和 "apple" 都能由詞典中的單詞組成。但是 "apple" 的字典序小于 "apply"      

提示：

• 所有輸入的字元串

模拟

資料範圍很小，我們可以直接模拟來做。

先将所有的 存入 ​​

​Set​

​​ 集合，友善後續可以近似 查詢某個子串是否存在

周遊 數組（題目沒有說 不重複，是以最好周遊剛剛預處理的 ​​

​Set​

​​ 集合），判斷每個

不算剪枝效果，該做法計算量不超過 ，可以過。

代碼：

class Solution {
    public String longestWord(String[] words) {
        String ans = "";
        Set<String> set = new HashSet<>();
        for (String s : words) set.add(s);
        for (String s : set) {
            int n = s.length(), m = ans.length();
            if (n < m) continue;
            if (n == m && s.compareTo(ans) > 0) continue;
            boolean ok = true;
            for (int i = 1; i <= n && ok; i++) {
                String sub = s.substring(0, i);
                if (!set.contains(sub)) ok = false;
            }
            if (ok) ans = s;
        }
        return      

• 時間複雜度：預處理​

  ​Set​

  ​​ 集合複雜度近似；判斷某個是否合法需要判斷所有子串是否均在中，複雜度為，其中為字元串長度，處理的過程還使用到​​

  ​compareTo​

  ​​ 操作，其複雜度為，其中和為參與比較的兩字元串長度，該操作相比于生成子串可忽略，而對于一個長度為的字元串而言，生成其所有的子串的計算量為首項為，末項為，公差為的等差數列求和結果。整體複雜度為
• 空間複雜度：

Trie

上述解法中「枚舉某個 的所有子串，并判斷子串是否在

不了解「Trie / 字典樹」的同學可以看前置 🧀：​​字典樹入門​​。裡面通過圖例展示了字典樹基本形态，以及提供了「數組實作」和「TrieNode 實作」兩種方式，還有「數組大小估算方式」和「Trie 應用面」介紹。

回到本題，起始先将所有的

對于某個 而言，其能成為「合法單詞」的充要條件為：

一些細節：為了防止每個樣例都 ​

​new​

​​ 大數組，我們使用 ​

​static​

​ 進行優化，并在跑樣例前進行相應的清理工作。

代碼：

class Solution {
    static int N = 30010, M = 26;
    static int[][] tr = new int[N][M];
    static boolean[] isEnd = new boolean[N];
    static int idx = 0;
    void add(String s) {
        int p = 0, n = s.length();
        for (int i = 0; i < n; i++) {
            int u = s.charAt(i) - 'a';
            if (tr[p][u] == 0) tr[p][u] = ++idx;
            p = tr[p][u];
        }
        isEnd[p] = true;
    }
    boolean query(String s) {
        int p = 0, n = s.length();
        for (int i = 0; i < n; i++) {
            int u = s.charAt(i) - 'a';
            p = tr[p][u];
            if (!isEnd[p]) return false;
        }
        return true;
    }
    public String longestWord(String[] words) {
        Arrays.fill(isEnd, false);
        for (int i = 0; i <= idx; i++) Arrays.fill(tr[i], 0);
        idx = 0;

        String ans = "";
        for (String s : words) add(s);
        for (String s : words) {
            int n = s.length(), m = ans.length();
            if (n < m) continue;
            if (n == m && s.compareTo(ans) > 0) continue;
            if (query(s)) ans = s;
        }
        return      

• 時間複雜度：将所有存入字典樹的複雜度為；查詢每個是否合法的複雜度為，其中為目前長度。整體複雜度為
• 空間複雜度：

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.720​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。