从小白开始刷算法 前缀树篇 leetcode.720

// 仅是我的思路代码，leetcode上大神更厉害
class Solution {
  public String longestWord(String[] words) {
      TrieNode trie = new TrieNode();
      for (String word : words) {
          trie.insert(word);
      }
      String longestWord = "";
      for (String word : words) {
          //判断其长度是否大于当前最长单词的长度，或者长度相等但字典序更小
          if (word.length() > longestWord.length() ||
                  (word.length() == longestWord.length() && word.compareTo(longestWord) < 0)) {
              if(trie.isWordChain(word))
              longestWord = word;
          }
      }
      return longestWord;
  }
}
class TrieNode {
  private TrieNode[] children;
  private boolean isEndOfWord;
  public TrieNode() {
      children = new TrieNode[26];
      isEndOfWord = false;
  }
  public void insert(String word) {
      TrieNode curr = this;
      for (char c : word.toCharArray()) {
          int index = c - 'a';
          if (curr.children[index] == null) {
              curr.children[index] = new TrieNode();
          }
          curr = curr.children[index];
      }
      curr.isEndOfWord = true;
  }
  public boolean isWordChain(String word) {
      TrieNode curr = this;
      for (char c : word.toCharArray()) {
          int index = c - 'a';
          //检查当前节点 curr 的子节点 children[index] 是否为空，
          //或者子节点 children[index] 不是一个结束节点（即该字符不是一个完整的单词）。
          if (curr.children[index] == null || !curr.children[index].isEndOfWord) {
              //给定的单词 word 在字典树中不存在，返回 false，表示不是一个有效的单词链。
              return false;
          }
          //更新当前节点 curr 为子节点 children[index]，继续遍历下一个字符。
          curr = curr.children[index];
      }
      //如果成功遍历完给定单词的所有字符，且每个字符都在字典树中存在且构成有效的单词链（即所有字符都是完整的单词），则返回 true，表示是一个有效的单词链。
      return true;
  }
}