package com.fishercoder.solutions;

/**
 * 758. Bold Words in String
 *
 * Given a set of keywords words and a string S, make all appearances of all keywords in S bold. Any letters between <b> and </b> tags become bold.
 * The returned string should use the least number of tags possible, and of course the tags should form a valid combination.
 * For example, given that words = ["ab", "bc"] and S = "aabcd", we should return "a<b>abc</b>d".
 * Note that returning "a<b>a<b>b</b>c</b>d" would use more tags, so it is incorrect.

 Note:

 words has length in range [0, 50].
 words[i] has length in range [1, 10].
 S has length in range [0, 500].
 All characters in words[i] and S are lowercase letters.

 */

public class _758 {
  public static class Solution1 {
    /**Interestingly, this problem is exactly the same as 616, using 616's code could get it AC'ed.*/
    public String boldWords(String[] words, String S) {
      boolean[] shouldBold = new boolean[S.length()];
      for (int i = 0, end = 0; i < S.length(); i++) {
        for (String word : words) {
          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();
    }
  }
}

@@ -33,742 +33,87 @@
 s;%0A%0A
-/**%0A * 758. Bold Words in String%0A *%0A * Given a set of keywords words and a string S, make all appearances of all keywords in S bold. Any letters between %3Cb%3E and %3C/b%3E tags become bold.%0A * The returned string should use the least number of tags possible, and of course the tags should form a valid combination.%0A * For example, given that words = %5B%22ab%22, %22bc%22%5D and S = %22aabcd%22, we should return %22a%3Cb%3Eabc%3C/b%3Ed%22.%0A * Note that returning %22a%3Cb%3Ea%3Cb%3Eb%3C/b%3Ec%3C/b%3Ed%22 would use more tags, so it is incorrect.%0A%0A Note:%0A%0A words has length in range %5B0, 50%5D.%0A words%5Bi%5D has length in range %5B1, 10%5D.%0A S has length in range %5B0, 500%5D.%0A All characters in words%5Bi%5D and S are lowercase letters.%0A%0A */%0A%0Apublic class _758 %7B%0A  public static class Solution1 %7B%0A    /**
+public class _758 %7B%0A    public static class Solution1 %7B%0A        /**%0A         * 
 Inte
@@ -204,11 +204,25 @@
 'ed.
-*/%0A
+%0A         */%0A    
     
@@ -279,16 +279,22 @@
 %7B%0A      
+  
+    
 boolean%5B
@@ -331,32 +331,38 @@
 ength()%5D;%0A      
+   
+   
 for (int i = 0, 
@@ -385,32 +385,40 @@
 ength(); i++) %7B%0A
+        
         for (Str
@@ -443,24 +443,34 @@
 %7B%0A          
+   
+       
 if (S.starts
@@ -498,16 +498,28 @@
         
+       
+     
 end = Ma
@@ -552,32 +552,42 @@
 h());%0A          
+         
+ 
 %7D%0A        %7D%0A    
@@ -580,26 +580,39 @@
         
+      
-%7D%0A
+  %7D%0A     
         
 shouldBo
@@ -603,16 +603,19 @@
         
+   
 shouldBo
@@ -637,24 +637,36 @@
 ;%0A      
-%7D%0A
+      %7D%0A     
       
+ 
 StringBu
@@ -704,24 +704,30 @@
 gBuilder();%0A
+      
       for (i
@@ -763,24 +763,32 @@
 ) %7B%0A        
+       
+ 
 if (!shouldB
@@ -793,24 +793,34 @@
 dBold%5Bi%5D) %7B%0A
+          
           st
@@ -862,16 +862,26 @@
         
+   
+       
 continue
@@ -882,34 +882,50 @@
 ntinue;%0A        
+       
+ 
 %7D%0A
+        
         int j = 
@@ -935,16 +935,24 @@
         
+     
+   
 while (j
@@ -981,24 +981,34 @@
 dBold%5Bj%5D) %7B%0A
+          
           j+
@@ -1018,26 +1018,41 @@
         
+   
-%7D%0A
+     %7D%0A       
         
 stringBu
@@ -1035,32 +1035,33 @@
 %0A               
+ 
 stringBuilder.ap
@@ -1102,16 +1102,24 @@
 %3C/b%3E%22);%0A
+        
         
@@ -1131,26 +1131,38 @@
  - 1;%0A      
+     
+ 
 %7D%0A
+      
       return
@@ -1192,16 +1192,22 @@
 ();%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 758