Solution

import java.util.List;

/*
 * @lc app=leetcode id=648 lang=java
 *
 * [648] Replace Words
 *
 * <https://leetcode.com/problems/replace-words/description/>
 *
 * algorithms
 * Medium (55.74%)
 * Likes:    642
 * Dislikes: 128
 * Total Accepted:    51.8K
 * Total Submissions: 92.6K
 * Testcase Example:  '["cat","bat","rat"]\\n"the cattle was rattled by the battery"'
 *
 * 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.
 * 
 * 
 * Example 1:
 * 
 * 
 * Input: dict = ["cat","bat","rat"], sentence = "the cattle was rattled by the
 * battery"
 * Output: "the cat was rat by the bat"
 * 
 * 
 * 
 * Constraints:
 * 
 * 
 * The input will only have lower-case letters.
 * 1 <= dict.length <= 1000
 * 1 <= dict[i].length <= 100
 * 1 <= sentence words number <= 1000
 * 1 <= sentence words length <= 1000
 * 
 * 
 */

// @lc code=start
class Solution {

    TrieNode root = new TrieNode();

    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isWord = false;
    }

    public String replaceWords(List<String> dict, String sentence) {
        for (String rootString : dict) {
            insertTrieNode(rootString);
        }
        String[] wordArray = sentence.split(" ");
        StringBuilder sb = new StringBuilder();
        for (String word : wordArray) {
            sb.append(findRoot(word));
            sb.append(" ");
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }

    /**
     * insert into trie
     * 
     * @param word
     */
    void insertTrieNode(String word) {
        TrieNode curNode = root;
        for (char c : word.toCharArray()) {
            if (curNode.children[c - 'a'] == null) {
                curNode.children[c - 'a'] = new TrieNode();
            }
            curNode = curNode.children[c - 'a'];
        }
        curNode.isWord = true;
    }

    String findRoot(String successor) {
        TrieNode curNode = root;
        StringBuilder rootString = new StringBuilder();
        for (char c : successor.toCharArray()) {
            if (curNode.isWord || curNode.children[c - 'a'] == null) {
                break;
            }
            rootString.append(c);
            curNode = curNode.children[c - 'a'];
        }
        if (curNode != root && curNode.isWord) {
            return rootString.toString();
        } else {
            return successor;
        }
    }
}
// @lc code=end

Similar