题目

https://leetcode.com/problems/longest-word-in-dictionary/

题解

建立一个 Trie，在 insert 的过程中，除最后一个节点外，如果一路上每一个节点都 isEnd，则将其返回值 diff 设置为 false，表明它的差异可以被容忍，可参与最后的长度比较。

class Node {
    Node[] map;
    boolean isEnd;

    public Node() {
        this.map = new Node['z' - 'a' + 1];
    }

    public Node get(char c) {
        return map[c - 'a'];
    }

    public Node put(char c) {
        Node node = new Node();
        map[c - 'a'] = node;
        return node;
    }
}

class Trie {
    Node node;

    public Trie() {
        node = new Node();
    }

    public boolean insert(String word) {
        char[] chars = word.toCharArray();
        Node cur = node;
        boolean diff = false;
        for (int i = 0; i < chars.length; i++) {
            if (cur.get(chars[i]) != null) {
                cur = cur.get(chars[i]);
                if (!cur.isEnd) diff = true;
            } else {
                cur = cur.put(chars[i]);
                if (i != word.length() - 1) diff = true;
            }
            if (i == chars.length - 1) cur.isEnd = true;
        }
        return diff;
    }
}

class Solution {
    public String longestWord(String[] words) {
        Arrays.sort(words);

        Trie trie = new Trie();
        String result = "";
        for (String word : words) {
            if (!trie.insert(word)) result = word.length() > result.length() ? word : result;
        }
        return result;
    }
}