Java Solution 42ms Reduce the search range by initial characher


  • 0
    3
    public class Solution {
    public String replaceWords(List<String> dict, String sentence) {
        if(dict.size()==0) return sentence;
        List<String>[] cate=new ArrayList[26];
        for(String s:dict){
            char c=s.charAt(0);
            if(cate[c-'a']==null)  cate[c-'a']=new ArrayList<String>();
            cate[c-'a'].add(s);
        }
        
        String[] ss=sentence.split(" ");
        for(int i=0;i<ss.length;i++){
            char c=ss[i].charAt(0);
            String rep=ss[i];
            if(cate[c-'a']==null) continue;
            for(String ca:cate[c-'a']){
                if(itsroot(ca,rep)) rep=ca;
            }
            ss[i]=rep;
        }
        
        StringBuilder res=new StringBuilder(ss[0]);
        for(int i=1;i<ss.length;i++) res.append(" ").append(ss[i]);        
        return res.toString();
        
    }
    
    public boolean itsroot(String r,String s){
        if(r.length()>s.length()) return false;
        char[] rc=r.toCharArray();
        char[] sc=s.toCharArray();
        for(int i=0;i<rc.length;i++){
            if(rc[i]!=sc[i]) return false;
        }
        return true;
    }
    

    }


Log in to reply
 

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