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()];
            dict.toArray(dicts);
            
            Arrays.sort(dicts, (a,b)->a.length()-b.length());
            
            StringBuilder newSentence=new StringBuilder();
            String[] words=sentence.split(" ");
            newSentence.append(this.transform(dicts,words[0]));
            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){
        		if(word.startsWith(root)){
        			return root;
        		}
        	}
        	return word;
        }
    }
    

  • 0
    D

    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.