package leetcode;

import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.com/problems/replace-words/
 */
public class Problem648 {
    public String replaceWords(List<String> dict, String sentence) {
        // TODO
        return "";
    }

    public static void main(String[] args) {
        Problem648 prob = new Problem648();
        System.out.println(prob.replaceWords(Arrays.asList("cat", "bat", "rat"),
            "the cattle was rattled by the battery")); // the cat was rat by the bat
    }
}

@@ -16,33 +16,8 @@
 e;%0A%0A
-import java.util.Arrays;%0A
 impo
@@ -199,296 +199,2101 @@
     
-// TODO%0A        return %22%22;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem648 prob = new Problem648();%0A        System.out.println(prob.replaceWords(Arrays.asList(%22cat%22, %22bat%22, %22rat%22),%0A            %22the cattle was rattled by the battery%22)); // the cat was rat by the bat
+Trie trie = new Trie();%0A        for (String word : dict) %7B%0A            trie.add(word);%0A        %7D%0A        String%5B%5D words = sentence.split(%22%5C%5Cs+%22);%0A        StringBuilder sb = new StringBuilder();%0A        int i = 0;%0A        for (String word : words) %7B%0A            if (i %3E 0) %7B%0A                sb.append(%22 %22);%0A            %7D%0A            sb.append(trie.get(word));%0A            i++;%0A        %7D%0A        return sb.toString();%0A    %7D%0A%0A    private static class Node %7B%0A        private Character ch;%0A        private boolean isWord;%0A        private Node%5B%5D nodes = new Node%5B26%5D;%0A%0A        public Node(Character ch, boolean isWord) %7B%0A            this.ch = ch;%0A            this.isWord = isWord;%0A        %7D%0A    %7D%0A%0A    private static class Trie %7B%0A        private final Node%5B%5D nodes = new Node%5B26%5D;%0A%0A        public void add(String str) %7B%0A            add(str, 0, nodes);%0A        %7D%0A%0A        private static void add(String str, int idx, Node%5B%5D nodes) %7B%0A            if (str.length() == idx) %7B%0A                return;%0A            %7D%0A            char c = str.charAt(idx);%0A            Node n = nodes%5Bc - 'a'%5D;%0A            if (n == null) %7B%0A                Node newNode = new Node(c, false);%0A                if (idx == str.length() - 1) %7B%0A                    newNode.isWord = true;%0A                %7D%0A                nodes%5Bc - 'a'%5D = newNode;%0A            %7D else %7B%0A                if (idx == str.length() - 1) %7B%0A                    n.isWord = true;%0A                %7D%0A            %7D%0A            add(str, idx + 1, nodes%5Bc - 'a'%5D.nodes);%0A        %7D%0A%0A        public String get(String str) %7B%0A            String s = get(str, 0, nodes);%0A            return (s == null) ? str : s;%0A        %7D%0A%0A        private static String get(String str, int idx, Node%5B%5D nodes) %7B%0A            if (str.length() == idx) %7B%0A                return null;%0A            %7D%0A            char c = str.charAt(idx);%0A            Node n = nodes%5Bc - 'a'%5D;%0A            if (n == null) %7B%0A                return null;%0A            %7D%0A            if (n.isWord) %7B%0A                return str.substring(0, idx + 1);%0A            %7D%0A            return get(str, idx + 1, n.nodes);%0A        %7D
 %0A   

Solve problem 648