My Java Solution


  • 0
    F

    bLens[i] represents the length of the longest sub string that can be contained by a pair of bold tags.

    public class Solution {
        public String addBoldTag(String s, String[] dict) {
            if(s==null || s.length()==0 || dict==null || dict.length==0) {
                return s;
            } else {
                int[] bLens = new int[ s.length() ];
                int start = 0, end = -1;
                StringBuilder sb = new StringBuilder();
                
                for(int idx = 0; idx < s.length(); idx++) {
                    for(String w:dict) {
                        if(s.startsWith(w, idx)) {
                            bLens[ idx ] = Math.max(bLens[ idx ], w.length());
                        }
                    }
                }
                
                for(int idx = 0; idx < bLens.length; idx++) {
                    if(bLens[ idx ] == 0) {
                        if(idx > end) {
                            sb.append(s.substring(idx, idx+1));
                        } else if(idx == end) {
                            sb.append("<b>").append(s.substring(start, end)).append("</b>");
                            sb.append(s.substring(idx, idx+1));
                        }
                    } else {
                        if(idx > end) {
                            start = idx;
                            end = idx+bLens[ idx ];
                        } else {
                            end = Math.max(end, idx+bLens[ idx ]);
                        }
                    }
                }
                if(end == bLens.length) {
                    sb.append("<b>").append(s.substring(start, bLens.length)).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.