My Java Solution using an int array


  • 0
    F

    Please find the inline explanation in the code

    class Solution {
        public String addBoldTag(String s, String[] dict) {
            if (s==null || s.length()==0) {
                return s;
            } else {
                StringBuilder sb = new StringBuilder();
                // ranges[i]=The maximum length of the string that matches the substring of s starting from i
                int[] ranges = new int[s.length()];
                // curEnd=The first idx beyond the currently 'covered' range. 
                // A range of string s is covered if it's enclosed within a pair of <b></b>
                int curEnd = -1;
                
                for (int idx = 0; idx < s.length(); idx++) {
                    for (String w:dict) {
                        if (s.startsWith(w, idx)) {
                            ranges[idx] = Math.max(ranges[idx], w.length());
                        }
                    }
                }
                for (int idx = 0; idx < ranges.length; idx++) {
                    if (idx <= curEnd) {
                        if (idx == curEnd) {
                            // If idx is the first index right after the currently covered range,
                            // then we should check if the substring starting from idx has a matched word in dict,
                            // i.e., check whether ranges[idx]>0 or not.
                            // If ranges[idx]>0, then the substring starting from idx has a matched word, and we should
                            // extend the covered range.
                            // Otherwise, we should enclose the current cover range with </b>
                            // Finally, we should append the current character to our new string
                            if (ranges[idx] > 0) {
                                curEnd = idx+ranges[idx];
                            } else {
                                sb.append("</b>");
                            }
                        } else {
                            // If idx is still within the current cover range, then we should try to extend
                            // the current cover range, and append the current character to the new string.
                            curEnd = Math.max(curEnd, idx+ranges[idx]);
                        }
                    } else {
                        if (ranges[idx] > 0) {
                            // idx is already beyond the current cover range, and even beyond the first index after 
                            // the current cover range. In this case, we should check whether idx is the start
                            // of a new cover range by checking whether ranges[idx] is zero or not.
                            // If ranges[idx]>0, then idx is the start of a new cover range, and we should first 
                            // append a <b> to our new string, and then update curEnd. Finally, we should append the 
                            // current character to the new string.
                            sb.append("<b>");
                            curEnd = idx+ranges[idx];
                        } // Otherwise, we just need to append the current character to our new string
                    }
                    // In all cases, the current character needs to be appended. So we can do it in the end, with one shot.
                    sb.append(s.charAt(idx));
                }
                if (curEnd == ranges.length) {
                    // enclose the cover range at the end of the string
                    sb.append("</b>");
                }
                
                return sb.toString();
            }
        }
    }
    

Log in to reply
 

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