Java O(KN) solution, k=length of longest string in dict, N=s.length();


  • 0

    Didn't notice the "The given dict ..., and its length won't exceed 100."
    So this solution is slow for the given test cases. But it should be good for extremely large dict size.

    public class Solution {
        public String addBoldTag(String s, String[] dict) {
            if(dict==null || dict.length==0 || s==null) return s;
            //find the length of shortest and longest word in the dict
            int minLen=dict[0].length(), maxLen=dict[0].length();
            HashSet<String> dictSet=new HashSet<String>(Arrays.asList(dict));
            for(int i=1; i<dict.length; i++){
                if(dict[i].length()<minLen) minLen=dict[i].length();
                else if(dict[i].length()>maxLen) maxLen=dict[i].length();
            }
            //memo for the bold characters
            boolean[] boldChars=new boolean[s.length()];
            int lastBold =-1;
            for(int i=0; i<s.length(); i++){
                int upperBound=Math.min(i+maxLen-1, s.length()-1); //inclusive
                int lowerBound=Math.max(i+minLen-1, lastBold+1);
                for(int end=upperBound; end>=lowerBound; end--){
                    if(dictSet.contains(s.substring(i,end+1))){
                        for(int j=i; j<=end; j++) boldChars[j]=true;
                        lastBold=end;
                        break; //optimization: no need to check shorter string start from i
                    }
                }
            }
            //Generate the final output
            StringBuilder sb = new StringBuilder();
            int i=0;
            while(i < s.length()){
                if(boldChars[i]){
                    sb.append("<b>");
                    while(i<s.length() && boldChars[i]){
                        sb.append(s.charAt(i++));
                    }
                    sb.append("</b>");
                }else{
                    sb.append(s.charAt(i++));
                }
            }
            return sb.toString();
        }
    }
    

Log in to reply
 

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