648. Replace Words

The basic idea is simple:

1. Use trie to save words in dictionary;
2. Traverse words in the sentence to find the shortest prefix existed in the dictionary
3. Replace words with shortest prefix

class Trie {
    Trie array[] = new Trie[26];
    String word = null;
}

public void build(Trie trie, String word) {
    Trie current = trie;
    for(int i = 0; i < word.length(); i++) {
        int index = word.charAt(i) - 'a';
        if( current.array[index] == null )
            current.array[index] = new Trie();
        current = current.array[index];
    }
    current.word = word;
}

public String search(Trie trie, String word) {
    Trie current = trie;
    for(int i = 0; i < word.length(); i++) {
        int index = word.charAt(i) - 'a';
        if( current.array[index] == null )
            return word;
        current = current.array[index];
        if( current.word != null )
            return current.word;
    }
    return word;
}

public String replaceWords(List<String> dict, String sentence) {
    Trie root = new Trie();
    for(int i = 0; i < dict.size(); i++)
        build(root, dict.get(i));

    String wordArray[] = sentence.split("\\s+");
    StringBuilder sb = new StringBuilder("");
    for(int i = 0; i < wordArray.length; i++) {
        sb.append(search(root, wordArray[i]));
        if( i != wordArray.length - 1 )
            sb.append(" ");
    }
    return sb.toString();
}