题目
In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, the root an, followed by other, which can form another word another.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.

You need to output the sentence after the replacement.

答案

class Solution {
    class TrieNode {
        // Initialize your data structure here.
        public TrieNode() {
            children = new TrieNode[26];
            bLeaf = false;
        }
        int value;
        boolean bLeaf;
        TrieNode[] children;
    }

    private boolean charExist(char c, TrieNode curr) {
        return curr.children[c - 'a'] != null;
    }
    private TrieNode nextNode(char c, TrieNode curr) {
        return curr.children[c - 'a'];
    }
    private void insertChar(char c, TrieNode curr, TrieNode ins) {
        curr.children[c - 'a'] = ins;
    }

    TrieNode root;
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode curr = root;
        for(int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if(!charExist(c, curr)) {
                TrieNode newnode = new TrieNode();
                newnode.value = c;
                insertChar(c, curr, newnode);
            }
            // You will need to mark this node as leaf, even if it is not really a leaf in the tree
            // but it is a leaf for this particular string word

            curr = nextNode(c, curr);
            if(i == word.length() - 1)
                curr.bLeaf = true;
        }
    }

    // Build trie with the words in dict
    public String replaceWords(List<String> dict, String sentence) {
        root = new TrieNode();
        for(String s : dict)
            insert(s);

        String[] words = sentence.split(" ");
        StringBuilder sb = new StringBuilder();
        for(int j = 0; j < words.length; j++) {
            String w = words[j];
            TrieNode curr = root;
            StringBuilder sbw = new StringBuilder();
            int i;
            boolean seen_root = true;
            for(i = 0; i < w.length(); i++) {
                if(curr.bLeaf) break;
                char c = w.charAt(i);
                if(charExist(c, curr)) {
                    sbw.append(c);
                    curr = nextNode(c, curr);
                    continue;
                }
                else {
                    seen_root = false;
                }
            }
            if(seen_root && sbw.length() > 0) {
                sb.append(sbw.toString());
            }
            else {
                sb.append(words[j]);
            }
            if(j != words.length - 1) sb.append(" ");
        }
        return sb.toString();
    }
}