Java Trie Based Simple Iterative solution !!


  • 0
    S

    public class Solution {
    public Node root;
    public Solution(){
    root=new Node('/');
    }

    public void insert(String s){
        Node curr=root;
        for(int i=0;i<s.length();i++){
            int index= s.charAt(i)-'a';
            if(curr.ch[index]==null){
                curr.ch[index]=new Node(s.charAt(i));
            }
            curr=curr.ch[index];
        }
        curr.isLeaf=true;
    }
    
    public String searc(String s){
         Node curr=root;
        for(int i=0;i<s.length();i++){
            if(curr.isLeaf){
                return s.substring(0,i);
            }
            int index= s.charAt(i)-'a';
            if(curr.ch[index]==null){
               return null;
            }
            curr=curr.ch[index];
        }
        return curr.isLeaf ? s:null;
    

    }
    public class Node{
    public char data;
    public Node[] ch;
    public boolean isLeaf;
    public Node(char c){
    this.data=c;
    this.ch= new Node[26];
    this.isLeaf=false;
    }

    }
    public String replaceWords(List<String> dict, String sentence) {
        for(String s:dict){
            insert(s);
        }
        StringBuffer sb= new StringBuffer();
        for(String st: sentence.split(" ")){
            if(sb.length() > 0){
                sb.append(" ");
            }
            String ssss=searc(st);
            if(ssss==null){
                sb.append(st);
            }else{
                sb.append(ssss);
            }
        }
     return sb.toString();
    }
    

    }


Log in to reply
 

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