class TrieNode {
    char val;
    boolean end;
    String word;
    Map<Character, TrieNode> children;

    public TrieNode(char val, boolean end, String word) {
        this.val = val;
        this.end = end;
        this.word = word;
        this.children = new HashMap<>();
    }

    public TrieNode(char val, boolean end) {
        this(val, end, "");
    }

    public void add(char val, boolean end, String word) {
        this.children.put(val, new TrieNode(val, end, word));
    }

    public boolean contains(char val) {
        return this.children.containsKey(val);
    }

    public TrieNode get(char val) {
        return this.children.get(val);
    }

    public boolean isEnd() {
        return this.end;
    }
}

class Trie {
    TrieNode root;

    public Trie() {
        this.root = new TrieNode('!', false);
    }

    public void add(String word) {
        TrieNode current = this.root;
        for (int i = 0; i < word.length(); ++i) {
            final char letter = word.charAt(i);
            final boolean end = i == word.length() - 1;

            if (current.contains(letter)) {
                current = current.get(letter);
                if (end) {
                    current.end = true;
                    current.word = word;
                }
            } else {
                current.add(letter, end, word);
                current = current.get(letter);
            }
        }
    }

    public String get(String word) {
        TrieNode current = this.root;
        for (int i = 0; i < word.length(); ++i) {
            final char letter = word.charAt(i);
            final boolean end = i == word.length() - 1;
            if (current.isEnd()) return current.word;
            if (!current.contains(letter)) return "";
            current = current.get(letter);
            if (end && !current.isEnd()) return "";
            if (end) break;
        }

        return current.word;
    }
}

class Solution {
    public String replaceWords(List<String> dict, String sentence) {
        Trie trie = new Trie();
        List<String> res = new ArrayList<>();

        for (String word : dict) {
            trie.add(word);
        }

        for (String word : sentence.split(" ")) {
            final String trieWord = trie.get(word);
            if (trieWord == "") {
                res.add(word);
            } else {

                res.add(trieWord);
            }
        }

        return String.join(" ", res.toArray(new String[res.size()]));
    }
}