leetcode.com/problems/replace-words/solution/

class Solution {
    class Trie {
        Map<Character, Trie> children;
        boolean mark;

        Trie() {
            children = new HashMap();
            mark = false;
        }

        void insert(String s) {
            Trie node = this;
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if (node.children.containsKey(ch) == false) {
                    Trie newNode = new Trie();
                    node.children.put(ch, newNode);
                }
                node = node.children.get(ch);
                if (node.mark == true) break;
                if (i == s.length() - 1) {
                    node.mark = true;
                }
            }
        }
    }

    public String replaceWords(List<String> dict, String sentence) {
        Collections.sort(dict);
        Trie root = new Trie();
        for (int i = 0; i < dict.size(); i++) {
            root.insert(dict.get(i));
        }
        StringBuilder ans = new StringBuilder();
        int len = sentence.length();
        int i = 0;
        char ch;
        while (i < len) {
            while (i < len && sentence.charAt(i) == ' ') {
                ans.append(' ');
                i++;
            }
            Trie node = root;
            while (i < len && sentence.charAt(i) != ' ') {
                ch = sentence.charAt(i);
                if (node == null) {
                    ans.append(ch);
                } else if (node.mark == true) {

                } else {
                    node = node.children.getOrDefault(ch, null);
                    ans.append(ch);
                }
                i++;
            }
        }
        return ans.toString();
    }
}