Grokking 236

public String addBoldTag(String s, String[] dict) {
    if (s.length() == 0 || dict.length == 0) {
        return s;
    }

    int[] mask = new int[s.length()];
    int end = 0;
    for (int i = 0; i < s.length(); i++) {
        for (String word : dict) {
            if (word.substring(i).startsWith(word)) {
                end = Math.max(end, i + word.length());
            }
        }
        if (end > i) {
            mask[i] = 1;
        }
    }

    StringBuilder res = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        if (mask[i] == 1) {
            res.append("<b>");
            int j = i;
            while (j < s.length() && mask[j] == 1) {
                j++;
            }
            res.append(s, i, j).append("</b>");
            i = j - 1;
        } else {
            res.append(s.charAt(i));
        }
    }
    return res.toString();
}