[JAVA] Trie / T : O(N + M), S : (26 * longest word)


  • 0
    J
    class Solution {
        
        class TrieNode{
            TrieNode[] tries;
            boolean exist;
            String value;
            public TrieNode(){
                this.tries = new TrieNode[26];
                this.exist = false;
            }
        }
        
        public String replaceWords(List<String> dict, String sentence) {
            TrieNode root = new TrieNode();
            
            for(String word : dict){
                char[] chs = word.toCharArray();
                TrieNode cur = root;
                for(char ch : chs){
                    if(cur.tries[ch - 'a'] == null){
                        cur.tries[ch - 'a'] = new TrieNode();
                    }
                    cur = cur.tries[ch - 'a'];
                }
                cur.exist = true;
                cur.value = word;
            }
            
            String[] strs = sentence.split(" ");
            StringBuffer strbuf = new StringBuffer();
            for(String word : strs){
                // Search minimized word
                char[] chs = word.toCharArray();
                TrieNode cur = root;
                for(char ch : chs){
                    if(cur.tries[ch - 'a'] == null){
                        break;
                    }
                    else if(cur.tries[ch - 'a'].exist == true){
                        word = cur.tries[ch - 'a'].value;
                        break;
                    }
                    
                    cur = cur.tries[ch - 'a'];
                }
                strbuf.append(word);
                strbuf.append(" ");
            }
            
            return strbuf.deleteCharAt(strbuf.length()-1).toString();
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.