# 0616. Add Bold Tag in String
###### tags: `Leetcode` `FaceBook` `Medium` `Merge Interval-Jump Game`
Link: https://leetcode.com/problems/add-bold-tag-in-string/
## 思路
思路二跑出来的结果比思路一快
### 思路一
merge interval的方法，很巧妙
和[55.Jump Game](https://hackmd.io/BLDJgdvVR2yk2ZZka2dArg)思路有点像
一直记录从现在这个位置i能到达的最远位置end，如果end>i，那么这个位置填true
### 思路二 O(M * N) M是s的长度 N是words里面所有word的长度和
对于每个word而言，先用```s.indexOf(word, startPosition)```找到它出现的位置
然后用一个array记录每个位置应不应该在bold里面
一开始的方法是像line 11-15一样，把每个位置标记成true
但是更简单的方法是只在首尾标记，然后用prefix sum算出这个位置在不在bold里面
注：indexOf(s, word)的复杂度是O(m * n), m是s的长度，n是word的长度
## Code
### 思路一

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 = end>(i + word.length())?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();
    }
}

### 思路二

class Solution {
    public String addBoldTag(String s, String[] words) {
        int len = s.length();
        int[] isBold = new int[len+1];
        for(String word:words){
            int idx = s.indexOf(word);
            while(idx != -1){
                int start = idx;
                int end = word.length()+idx;
                
                // for(int i = start;i < end;i++){
                //     if(!isBold[i]){
                //         isBold[i] = true;
                //     }
                // }
                
                isBold[start]++;
                isBold[end]--;
                
                idx++;
                idx = s.indexOf(word, idx);
            }
        }
        
        StringBuilder sb = new StringBuilder();
        boolean inBold = false;
        int prev = 0;
        for(int i = 0;i <= len;i++){
            int curr = prev+isBold[i];
            if(prev == 0 && curr > 0){
                sb.append("<b>");
                inBold = true;
            }
            if(prev > 0 && curr == 0){
                sb.append("</b>");
                inBold = false;
            }
            if(i == len) break;
            sb.append(s.charAt(i));
            prev = curr;
        }
        return sb.toString();
    }
}