最长单词

给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。

示例：

输入： ["cat","banana","dog","nana","walk","walker","dogwalker"]
输出： "dogwalker"
解释： "dogwalker"可由"dog"和"walker"组成。
提示：

0 <= len(words) <= 200
1 <= len(words[i]) <= 100
通过次数3,239提交次数8,452

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-word-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {                                                                //树结点
    class TreeNode {
        private boolean isEnd;
        private TreeNode[] next;
        TreeNode() {
            this.isEnd = false;
            this.next = new TreeNode[26];
        }
    }

    class Tree {                                                                 //字典树类
        private TreeNode root;
        
        Tree() {
            this.root = new TreeNode();
        }

        public void insert(String word) {
            TreeNode curr = root;
            for (int i = 0; i < word.length(); i++) {
                int node = word.charAt(i) - 'a';
                if (curr.next[node] == null) curr.next[node] = new TreeNode();
                curr = curr.next[node];
            }
            curr.isEnd = true;                                                  //标记尾结点
        }

        public TreeNode getRoot() {
            return root;
        }
    }
    private Tree tree;
    boolean flag = false;                                                       //出现过别的单词
    boolean finish = false;                                                     //是否完成搜索
    public String longestWord(String[] words) {
        this.tree = new Tree();
        Arrays.sort(words, (o1, o2) -> {                                        //对每隔单词按照长度和字典序排序（长度相同时按照字典序）
            if (o1.length() == o2.length())
                return o1.compareTo(o2);
            else {
                return Integer.compare(o2.length(), o1.length());
            }
        });

        for (String x : words) {                                                //构造字典树
            tree.insert(x);
        }

        for (int i = 0; i < words.length; i++) {
            flag = false;                                                       //对每个单词进行搜索
            if (words[i].length() == 0) continue;
            dfs(0, words[i], tree.getRoot());                                   //传入当前字符索引，需要开始搜索的结点
            if (finish) return words[i];
        }
        return "";
    }

    private void dfs(int index, String word, TreeNode root) {
        if (index >= word.length()) return;

        int i = word.charAt(index) - 'a';
        root = root.next[i];

        if (root == null) return;
        if (index == word.length() - 1) {
            if (flag && root.isEnd) finish = true;                              //如果字符是单词并且前一部分由单词构成
        }
        if (root.isEnd && !flag) {                                              //当前结点是单词，但是之前不是单词构成的
            flag = true;
            dfs(index + 1, word, tree.getRoot());                               //从下一个字符开始，从头结点开始搜索是否可有新的单词构成
            if (finish) return;
            flag = false;
        } else if (root.isEnd && flag) {                                        //当前是单词并且已经有单词构成
            dfs(index + 1, word, tree.getRoot());
            if (finish) return;
        }
        dfs(index + 1, word, root);                                             //一般情况
        if (finish) return;
    }
}


作者：ppppjcute
链接：https://leetcode-cn.com/problems/longest-word-lcci/solution/java-shi-yong-zi-dian-shu-jin-xing-qian-zhui-cha-x/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信