Java Solution 42ms Reduce the search range by initial characher

  • 0
    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>();
        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;
        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.