leetcode
leetcode 651 ~ 700
字符串中的加粗单词

字符串中的加粗单词

难度:

标签:

题目描述

代码结果

运行时间: 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数组中对应单词覆盖的每个位置都设为True来实现。因此,如果单词'ab'和'bc'在字符串'sabc'中重叠,首先单词'ab'会使mask数组在位置0和1设为True,然后单词'bc'会使mask数组在位置1和2设为True。结果是,mask数组的前三个位置都标记为True,正确地表示这些位置的字符都应被加粗。这种方法能够自然地处理单词的重叠情况,无需额外逻辑。
🦆
如果单词列表中有重复的单词,算法是否进行了冗余操作,有没有更高效的处理方法?
如果单词列表中包含重复的单词,当前算法会对每次出现的单词都执行查找和标记操作,这确实是一种冗余操作。更高效的处理方法是先使用集合或其他数据结构去除单词列表中的重复项,然后再进行查找和标记。这样可以减少不必要的查找次数,提高算法的效率。
🦆
在构造最终的加粗字符串时,为什么选择在遇到mask[i]为True且i为0或mask[i-1]为False时插入标签?这样的条件判断是否能覆盖所有需要加粗的场景?
这种条件判断方式是为了识别加粗区域的开始边界。当mask[i]为True且i为0时,说明字符串的第一个字符需要加粗;若mask[i]为True且mask[i-1]为False时,则表示当前字符是一个新的加粗区域的开始。这种方式能够确保每次进入一个加粗区域时只插入一次标签,并且可以正确处理连续的加粗区域。因此,这个条件判断可以覆盖所有需要加粗的场景,包括连续加粗和非连续加粗的情况。
🦆
算法中idx变量在while循环中只在找到单词后才自增,这是否可能导致无限循环?如果find方法返回-1,循环如何终止?
算法确保了循环不会陷入无限循环。在while循环中,每次找到单词后,idx变量自增1,确保下次find操作从上一次找到的单词的下一个位置开始搜索。如果find方法返回-1,表示字符串中已经没有更多的该单词,此时while循环的条件'-1 < idx < len(s)'不再满足,因此循环会自然终止。这样的逻辑确保了循环的正确性和终止。

相关问题