package com.fishercoder.solutions;

/**
 * 616. Add Bold Tag in String
 *
 * Given a string s and a list of strings dict,
 * you need to add a closed pair of bold tag <b> and </b>
 * to wrap the substrings in s that exist in dict.
 * If two such substrings overlap, you need to wrap them together by only one pair of closed bold tag.
 * Also, if two substrings wrapped by bold tags are consecutive, you need to combine them.

 Example 1:
 Input:
 s = "abcxyz123"
 dict = ["abc","123"]
 Output:
 "<b>abc</b>xyz<b>123</b>"

 Example 2:
 Input:
 s = "aaabbcc"
 dict = ["aaa","aab","bc"]
 Output:
 "<b>aaabbc</b>c"

 Note:
 The given dict won't contain duplicates, and its length won't exceed 100.
 All the strings in input have length in range [1, 1000].
 */
public class _616 {

    /**credit: https://discuss.leetcode.com/topic/92112/java-solution-boolean-array*/
    public String addBoldTag(String s, String[] dict) {
        boolean[] shouldBold = 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());
                }
            }
            shouldBold[i] = end > i;
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (!shouldBold[i]) {
                stringBuilder.append(s.charAt(i));
                continue;
            }
            int j = i;
            while (j < s.length() && shouldBold[j]) {
                j++;
            }
            stringBuilder.append("<b>" + s.substring(i, j) + "</b>");
            i = j - 1;
        }
        return stringBuilder.toString();
    }

}

@@ -774,19 +774,71 @@
  %7B%0A%0A    
-/**
+public static class Solution1 %7B%0A        /**%0A         * 
 credit: 
@@ -909,15 +909,29 @@
 rray
+%0A         
 */%0A    
+ 
+   
 publ
@@ -986,16 +986,20 @@
         
+    
 boolean%5B
@@ -1038,16 +1038,20 @@
 gth()%5D;%0A
+    
         
@@ -1106,24 +1106,28 @@
             
+    
 for (String 
@@ -1133,32 +1133,36 @@
  word : dict) %7B%0A
+    
                 
@@ -1210,16 +1210,20 @@
         
+  
+  
 end = Ma
@@ -1262,34 +1262,42 @@
                 
-%7D%0A
+    %7D%0A    
             %7D%0A  
@@ -1306,16 +1306,20 @@
         
+ 
+   
 shouldBo
@@ -1343,26 +1343,33 @@
         
-%7D%0A
+    %7D%0A   
         
 StringBu
@@ -1360,16 +1360,17 @@
         
+ 
 StringBu
@@ -1412,32 +1412,36 @@
 lder();%0A        
+    
 for (int i = 0; 
@@ -1471,24 +1471,28 @@
             
+ 
+   
 if (!shouldB
@@ -1509,32 +1509,36 @@
                 
+  
+  
 stringBuilder.ap
@@ -1572,16 +1572,20 @@
         
+    
 continue
@@ -1586,16 +1586,20 @@
 ntinue;%0A
+    
         
@@ -1616,16 +1616,20 @@
         
+    
 int j = 
@@ -1627,24 +1627,28 @@
  int j = i;%0A
+    
             
@@ -1705,16 +1705,20 @@
         
+   
+ 
 j++;%0A   
@@ -1718,34 +1718,42 @@
 ++;%0A            
-%7D%0A
+    %7D%0A    
             stri
@@ -1818,16 +1818,20 @@
         
+ 
+   
 i = j - 
@@ -1833,34 +1833,42 @@
  j - 1;%0A        
-%7D%0A
+    %7D%0A    
         return s
@@ -1888,21 +1888,31 @@
 toString();%0A
+        %7D%0A
     %7D%0A%0A%7D%0A

refactor 616