gold-17-15

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

示例：

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

提示：

• 0 <= len(words) <= 200
• `1 <= len(words[i]) <= 100

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    private int maxLen = 0;
    private String result = "";

    public String longestWord(String[] words) {
        Trie root = new Trie();

        for (String word : words) {
            insertWord(root, word);
        }

        search(root, root);
        return result;
    }



    class Trie {
        Trie[] next;
        String curWord;
    }

    private void insertWord(Trie root, String word) {
        if (word == null || word.length() == 0) {
            return;
        }

        Trie cur = root;
        for (char ch : word.toCharArray()) {
            if (cur.next == null) {
                cur.next = new Trie[26];
            }

            if (cur.next[ch - 'a'] == null) {
                cur.next[ch - 'a'] = new Trie();
            }

            cur = cur.next[ch - 'a'];
        }

        cur.curWord = word;
    }

    private boolean matches(Trie root, String word) {
        if (word == null || word.length() == 0) {
            return false;
        }

        Trie cur = root;
        for (char ch : word.toCharArray()) {
            if (cur.next == null || cur.next[ch - 'a'] == null) {
                return false;
            }

            cur = cur.next[ch - 'a'];
        }

        return cur.curWord != null;
    }

    private boolean canSplit(Trie root, String word) {
        if (word == null || word.length() == 0) {
            return false;
        }

        Trie cur = root;
        for (char ch : word.toCharArray()) {
            if (cur.next == null || cur.next[ch - 'a'] == null) {
                return false;
            }

            cur = cur.next[ch - 'a'];
            if (cur.curWord != null) {
                String rightW = word.substring(cur.curWord.length());
                if (matches(root, rightW) || canSplit(root, rightW)) {
                    return true;
                }
            }
        }

        return false;
    }

    private void search(Trie root, Trie trie) {
        if (trie == null) {
            return;
        }

        if (trie.curWord != null && trie.curWord.length() > maxLen && canSplit(root, trie.curWord)) {
            maxLen = trie.curWord.length();
            result = trie.curWord;
        }

        if (trie.next != null) {
            for (Trie nextTrie : trie.next) {
                search(root, nextTrie);
            }
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)