Greedy Java Solution - 99ms

  • 0

    Greedy - Put shortest root first.

    public class Solution {
        public String replaceWords(List<String> dict, String sentence) {
            String[] dicts=new String[dict.size()];
            Arrays.sort(dicts, (a,b)->a.length()-b.length());
            StringBuilder newSentence=new StringBuilder();
            String[] words=sentence.split(" ");
            for(int i=1;i<words.length;i++){
            	newSentence.append(" "+this.transform(dicts, words[i]));
            return newSentence.toString();
        private String transform(String[] dicts, String word){
        	for(String root:dicts){
        			return root;
        	return word;

  • 0

    can you state time complexity of this.

  • 0

    @dillip Time complexity O(m*n):

    • m: the length of the dict
    • n: the number of words in the sentence

Log in to reply

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