字符串中的加粗单词
难度:
标签:
题目描述
代码结果
运行时间: 41 ms, 内存: 16.1 MB
/*
* Problem: 758. Bold Words in String
* The problem requires the use of bold tags to mark the words present in the list 'dict' within the string 's'.
*
* Approach using Java Streams:
* 1. Create a boolean array 'bold' to mark positions in the string that need to be bolded.
* 2. Use streams to mark the positions of words found in 's'.
* 3. Generate the result string by inserting <b> and </b> tags as needed.
*/
import java.util.stream.IntStream;
public class Solution {
public String boldWords(String[] words, String S) {
boolean[] bold = new boolean[S.length()];
IntStream.range(0, words.length).forEach(i -> {
String word = words[i];
IntStream.iterate(S.indexOf(word), start -> start != -1, start -> S.indexOf(word, start + 1)).forEach(start -> {
IntStream.range(start, start + word.length()).forEach(j -> bold[j] = true);
});
});
StringBuilder result = new StringBuilder();
IntStream.range(0, S.length()).forEach(i -> {
if (bold[i] && (i == 0 || !bold[i - 1])) result.append("<b>");
result.append(S.charAt(i));
if (bold[i] && (i == S.length() - 1 || !bold[i + 1])) result.append("</b>");
});
return result.toString();
}
}
解释
方法:
本题的解题思路是:先初始化一个布尔数组 mask,长度与字符串 s 相同,用于标记 s 中每个字符是否属于加粗单词。然后遍历单词列表 words,对于每个单词,用 find 方法在 s 中查找该单词出现的位置,并将 mask 数组中对应位置的值设为 True。最后遍历 mask 数组,根据当前字符是否被标记以及前后字符的标记情况,在合适的位置插入 和 标签,构造出最终的结果字符串。
时间复杂度:
O(mn)
空间复杂度:
O(n)
代码细节讲解
🦆
在查找单词并标记mask数组时,您如何处理重叠单词的情况,例如单词'ab'和'bc'在字符串'sabc'中重叠?
▷🦆
如果单词列表中有重复的单词,算法是否进行了冗余操作,有没有更高效的处理方法?
▷🦆
在构造最终的加粗字符串时,为什么选择在遇到mask[i]为True且i为0或mask[i-1]为False时插入标签?这样的条件判断是否能覆盖所有需要加粗的场景?
▷🦆
算法中idx变量在while循环中只在找到单词后才自增,这是否可能导致无限循环?如果find方法返回-1,循环如何终止?
▷