share Java Solution using TrieTree


  • 0
    T
    public class Solution {
        class TrieNode{
            TrieNode[] children;
            String word;
            TrieNode(){
                children=new TrieNode[26];
            }
            
        }
        
        public String replaceWords(List<String> dict, String sentence) {
               TrieNode root=new TrieNode();
               for(String ele:dict){
                    constructTree(root,ele);  
               } 
              StringBuilder sb=new StringBuilder();
              for(int i=0;i<sentence.length();i++){
                  if(sentence.charAt(i)==' '){
                      sb.append(" ");
                      continue;
                  }
                  
                  int j=i;
                  while(j+1<sentence.length()&&sentence.charAt(j+1)>='a'&&sentence.charAt(j+1)<='z'){
                        j++;
                  }
                  
                  String temp=sentence.substring(i,j+1);
                  String find=findminstr(root,temp);
                  sb.append(find);
                  i=j;
              }
            
             return sb.toString();
        }
        
        public String findminstr(TrieNode root,String str){
            char[] array=str.toCharArray();
            TrieNode current=root;
            
            for(int i=0;i<array.length;i++){
                char c=array[i];
                if(current.children[c-'a']==null){
                    return str;
                }
                current=current.children[c-'a'];
                if(current.word!=null){
                    return current.word;
                }
            }
            return str;
        }
        
        public void constructTree(TrieNode root,String str){
            char[] array=str.toCharArray();
            TrieNode current=root;
            for(int i=0;i<array.length;i++){
                   if(current.children[array[i]-'a']==null){
                       current.children[array[i]-'a']=new TrieNode();
                   }
                   current=current.children[array[i]-'a'];
            }
            current.word=str;
        }
    }
    

Log in to reply
 

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