关于后端:面试高频题难度-15可用-Trie-进阶的模拟题

50次阅读

共计 2816 个字符,预计需要花费 8 分钟才能阅读完成。

题目形容

这是 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" 

提醒:

  • $1 <= words.length <= 1000$
  • $1 <= words[i].length <= 30$
  • 所有输出的字符串 $words[i]$ 都只蕴含小写字母。

模仿

数据范畴很小,咱们能够间接模仿来做。

先将所有的 $words[i]$ 存入 Set 汇合,不便后续能够近似 $O(1)$ 查问某个子串是否存在 $words$ 中。

遍历 $words$ 数组(题目没有说 $words$ 不反复,因而最好遍历刚刚预处理的 Set 汇合),判断每个 $words[i]$ 是否为「非法单词」,同时利用以后的最长单词来做剪枝。

不算剪枝成果,该做法计算量不超过 $10^6$,能够过。

代码:

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 ans;
    }
}
  • 工夫复杂度:预处理 Set 汇合复杂度近似 $O(n)$;判断某个 $words[i]$ 是否非法须要判断所有子串是否均在 $words$ 中,复杂度为 $O(m^2)$,其中 $m$ 为字符串长度,解决 $words[i]$ 的过程还应用到 compareTo 操作,其复杂度为 $O(\min(N, M))$,其中 $N$ 和 $M$ 为参加比拟的两字符串长度,该操作相比于生成子串可疏忽,而对于一个长度为 $m$ 的字符串而言,生成其所有的子串的计算量为首项为 $1$,末项为 $m$,公差为 $1$ 的等差数列求和后果。整体复杂度为 $O(\sum_{i = 0}^{n – 1}words[i].length^2)$
  • 空间复杂度:$O(\sum_{i = 0}^{n – 1}words[i].length)$

Trie

上述解法中「枚举某个 $words[i]$ 的所有子串,并判断子串是否在 $words$ 数组中呈现」的操作可应用「字典树」来实现。

不理解「Trie / 字典树」的同学能够看前置 🧀:字典树入门。外面通过图例展现了字典树根本状态,以及提供了「数组实现」和「TrieNode 实现」两种形式,还有「数组大小估算形式」和「Trie 利用面」介绍。

回到本题,起始先将所有的 $words[i]$ 存入字典树,并记录每个字符的结尾编号。

对于某个 $words[i]$ 而言,其能成为「非法单词」的充要条件为:$words[i]$ 的每个前缀编号都有「以结尾编号」所被记录。

一些细节:为了避免每个样例都 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 ans;
    }
}
  • 工夫复杂度:将所有 $words[i]$ 存入字典树的复杂度为 $O(\sum_{i = 0}^{n – 1}words[i].length)$;查问每个 $words[i]$ 是否非法的复杂度为 $O(m)$,其中 $m$ 为以后 $words[i]$ 长度。整体复杂度为 $O(\sum_{i = 0}^{n – 1}words[i].length)$
  • 空间复杂度:$O(C)$

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.720 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。

在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSou…。

在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布

正文完
 0