Java Trie Solution


  • 0
    A

    Simple, Just make a trie with dictionary and then for every word in the sentence look it up in trie, if during you find isw as true, which means it is a smallest root for this word, add it to the result or add the whole word.

    
    class Solution {
        // Trie Node
        class Node{
        	char alp;
        	Node[] map;
        	boolean isw;  // is it a word or no?
        	Node(){
        		map=new Node[26];
        	}
        }
    
        Node root;
    
        public String replaceWords(List<String> dict, String sentence) {
     	     root=new Node();
     	     for(String s:dict){
     	     	Node next=root;
     	     	for(char c:s.toCharArray()){
     	     		if(next.map[c-'a']==null) next.map[c-'a']=new Node(); 
                    next=next.map[c-'a'];
     	     		next.alp=c;
     	     	}
     	     	next.isw=true;
     	     }
     	     StringBuilder result=new StringBuilder();
     	     String sentns[]=sentence.split(" ");
     	     for(String word:sentns){
     	     	Node next=root;
     	     	int i=1;
     	     	String add=word;
     	     	for(char c:word.toCharArray()){
     	     		if(next.map[c-'a']!=null)
     	     		{
     	     		next=next.map[c-'a'];
     	     		if(next.isw){
     	     			add=word.substring(0,i);
     	     			break;
     	     		}
     	     	}
     	     	else break;
     	     	i++;
     	     	}
     	     	result.append(add+" "); 	     			
     	     }
    
     	     return result.toString().trim();
        }
    
    

Log in to reply
 

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