public TrieNode(char val) {
childNode = new TrieNode[26];
root = new TrieNode(' ');
public void insert(String word, int index) {
if (word == null || word.length() == 0) {
for (char c : word.toCharArray()) {
if (curNode.childNode[pos] == null) {
curNode.childNode[pos] = new TrieNode(c);
curNode = curNode.childNode[pos];
public int searchPrefix(String word) {
if (word == null || word.length() == 0) {
for (char c : word.toCharArray()) {
if (curNode.childNode[pos] == null) {
else if (curNode.childNode[pos].isWord){
return curNode.childNode[pos].index;
curNode = curNode.childNode[pos];
public String replaceWords(List<String> dict, String sentence) {
if (dict.size() == 0 || sentence == null || sentence.length() == 0) {
for (int i = 0; i < dict.size(); i++) {
trie.insert(dict.get(i), i);
String[] words = sentence.split("\\s+");
for (int i = 0; i < words.length; i++) {
int index = trie.searchPrefix(words[i]);
words[i] = dict.get(index);
StringBuilder res = new StringBuilder();
for (int i = 0; i < words.length - 1; i++) {
res.append(words[words.length - 1]);