648.Replace Words

1-Naive

class Solution {
    public String replaceWords(List<String> dict, String sentence) {
        Set<String> set = new HashSet<>();

        for(String s : dict){
            set.add(s);
        }

        String[] words = sentence.split(" ");
        StringBuilder sb = new StringBuilder();

        for(String s : words){
            boolean isReplace = false;

            for(int i = 1; i < s.length(); i++){
                if(set.contains(s.substring(0, i))){
                    sb.append(s.substring(0, i));
                    sb.append(' ');
                    isReplace = true;
                    break;
                }    
            }
            if(!isReplace){
                sb.append(s);
                sb.append(' ');
            }
        }  
        return sb.toString().trim();
    }
}

2- Trie

class Solution {
    public String replaceWords(List<String> dict, String sentence) {
        String[] words = sentence.split(" ");
        TrieNode root = buildTrieTree(dict);
        return replaceWords(words, root);
    }
    public TrieNode buildTrieTree(List<String> dict){
        TrieNode root = new TrieNode(' ');
        for(String s : dict){
            TrieNode cur = root;
            for(char c : s.toCharArray()){
                if(cur.children[c - 'a'] == null){
                    cur.children[c - 'a'] = new TrieNode(c);
                }
                cur = cur.children[c - 'a'];
            }
            cur.isWord = true;
            cur.word = s;
        }
        return root;
    }
    public String replaceWords(String[] words, TrieNode root){
        StringBuilder sb = new StringBuilder();
        for(String word : words){
            sb.append(replace(word, root));
            sb.append(' ');
        }
        return sb.toString().trim();
    }

    public String replace(String word, TrieNode root){
        TrieNode cur = root;
        for(char c : word.toCharArray()){
            if(cur.children[c - 'a'] != null){
                if(cur.children[c - 'a'].isWord)
                    return cur.children[c - 'a'].word;
                else{
                    cur = cur.children[c - 'a'];
                }
            }
            else{
                break;
            }
        }
        return word;
    }
}

class TrieNode{
    char c;
    TrieNode[] children;
    boolean isWord;
    String word = null;
    public TrieNode(char c){
        this.c = c;
        this.children = new TrieNode[26];
        this.isWord = false;
        this.word = null;
    }
}