Java Solution with some optimizations (44ms)


  • 0
    S
    public class Solution {
        public String replaceWords(List<String> dict, String sentence) {
            HashSet<String> d = new HashSet<String>();
            int maxLen=0;
            for(String s : dict) {
                if (s.length()>maxLen) { 
                    maxLen=s.length();
                }
                d.add(s);
            }
            //System.out.println(maxLen);    
            StringBuilder ns = new StringBuilder("");
            String[] words=sentence.split(" ");
            for(int i=0;i<words.length;i++) {
                String lastStem=null;
                int len = Math.min(maxLen,words[i].length());
                for (int j=1;j<len+1;j++) { 
                    String frag=words[i].substring(0,j);
                    //System.out.println("Contains "+frag);
                    if (d.contains(frag)) { 
                        lastStem=frag;
                        break;
                    }
                }
                if (lastStem!=null) {
                    ns.append(lastStem);
                } else {
                    ns.append(words[i]);
                }
                if (i<words.length-1) { 
                        ns.append(" ");
                }
            }
            
            return ns.toString();
        }
    }
    

Log in to reply
 

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