14ms java solution, average O(s*l)


  • 0
    L
    public String addBoldTag(String s, String[] dict) {
    	boolean[] isBold = new boolean[s.length()];
    	for (String word : dict) {
    		int index = 0;
    		int pos = 0;
    		while (index >= 0 && index < s.length()) {
    			index = s.indexOf(word, index);
    			if (index != -1) {
    				for (pos = Math.max(pos, index); pos < index + word.length(); pos++) {
    					isBold[pos] = true;
    				}
    				index++;
    			}
    		}
    	}
    	StringBuilder out = new StringBuilder();
    	for (int i = 0; i < s.length(); i++) {
    		if (!isBold[i]) {
    			out.append(s.charAt(i));
    		} else {
    			int j = i;
    			while (j < s.length() && isBold[j]) {
    				j++;
    			}
    			out.append("<b>" + s.substring(i, j) + "</b>");
    			i = j - 1;
    		}
    	}
    	return out.toString();
    }
    

Log in to reply
 

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