题目

类型：数组

image.png

解题思路

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

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

一些细节：为了防止每个样例都 new 大数组，我们使用 static 进行优化，并在跑样例前进行相应的清理工作。

代码

  1. class Solution {
  2.     static int N = 30010, M = 26;
  3.     static int[][] tr = new int[N][M];
  4.     static boolean[] isEnd = new boolean[N];
  5.     static int idx = 0;
  6.     void add(String s) {
  7.         int p = 0, n = s.length();
  8.         for (int i = 0; i < n; i++) {
  9.             int u = s.charAt(i) - 'a';
  10.             if (tr[p][u] == 0) tr[p][u] = ++idx;
  11.             p = tr[p][u];
  12.         }
  13.         isEnd[p] = true;
  14.     }
  15.     boolean query(String s) {
  16.         int p = 0, n = s.length();
  17.         for (int i = 0; i < n; i++) {
  18.             int u = s.charAt(i) - 'a';
  19.             p = tr[p][u];
  20.             if (!isEnd[p]) return false;
  21.         }
  22.         return true;
  23.     }
  24.     public String longestWord(String[] words) {
  25.         Arrays.fill(isEnd, false);
  26.         for (int i = 0; i <= idx; i++) Arrays.fill(tr[i], 0);
  27.         idx = 0;
  29.         String ans = "";
  30.         for (String s : words) add(s);
  31.         for (String s : words) {
  32.             int n = s.length(), m = ans.length();
  33.             if (n < m) continue;
  34.             if (n == m && s.compareTo(ans) > 0) continue;
  35.             if (query(s)) ans = s;
  36.         }
  37.         return ans;
  38.     }
  39. }