Add Bold Tag in String

开始晃神了，还以为是dp。仔细一看，开个array就可以啦。一次AC

public class Solution {
    public String addBoldTag(String s, String[] dict) {
        boolean[] arr = new boolean[s.length()];
        StringBuilder sb = new StringBuilder(s);
        for(int i=1;i<=arr.length;i++){
            for(String d:dict){
                if(i-d.length()>=0 && sb.substring(i-d.length(),i).equals(d))
                    setArr(arr, i-d.length(),i-1);
            }
        }
        StringBuilder ans = new StringBuilder();
        for(int i=0;i<arr.length;){
            int idx = i;
            while(idx<arr.length&&arr[idx]==true)
                idx++;
            if(idx==i)
                ans.append(sb.charAt(i++));
            else{
                ans.append("<b>"+sb.substring(i,idx)+"</b>");
                i=idx;
            }
        }

        return ans.toString();
    }

    public void setArr(boolean[] arr, int start, int end){
        for(int i=start;i<=end;i++){
            arr[i] = true;
        }
    }
}

更简洁的解法是利用string.startsWith(substring, i)来进行设置。

public class Solution {
    public String addBoldTag(String s, String[] dict) {
        boolean[] bold = new boolean[s.length()];
        for (int i = 0, end = 0; i < s.length(); i++) {
            for (String word : dict) {
                if (s.startsWith(word, i)) {
                    end = Math.max(end, i + word.length());
                }
            }
            bold[i] = end > i;
        }

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (!bold[i]) {
                result.append(s.charAt(i));
                continue;
            }
            int j = i;
            while (j < s.length() && bold[j]) j++;
            result.append("<b>" + s.substring(i, j) + "</b>");
            i = j - 1;
        }

        return result.toString();
    }
}