Simple Java Solution Based On Trie (Beat 98%)


  • 0
    X
    class TrieNode{
        TrieNode[] children = new TrieNode[26];
        boolean isWord;
    }
    
    public class Solution {
        public String replaceWords(List<String> dict, String sentence) {
            TrieNode root = new TrieNode();
            for(String s : dict){
                buildTrie(root,s);
            }
            String[] words = sentence.split(" ");
            StringBuilder sb = new StringBuilder();
            for(String word : words){
                int n = search(root, word);
                sb.append(n==-1?word:word.substring(0, n));
                sb.append(" ");
            }
            return sb.toString().trim();
        }
        
        void buildTrie(TrieNode root, String word){
            for(int i=0;i<word.length();i++){
                int j = word.charAt(i) - 'a';
                if(root.children[j] == null){
                    root.children[j] = new TrieNode();
                }
                root = root.children[j];
            }
            root.isWord = true;
        }
        
        
    	int search(TrieNode root, String word) {
    		int len = 0;
    		for (int i = 0; i < word.length(); i++) {
    			int j = word.charAt(i) - 'a';
    			if (root.isWord)
    				return len;
    			if (root.children[j] == null)
    				return -1;
    
    			len++;
    			root = root.children[j];
    		}
    		return -1;
    	}
    }
    

Log in to reply
 

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