leetcode
leetcode 701 ~ 750
情感丰富的文字

情感丰富的文字

难度:

标签:

题目描述

代码结果

运行时间: 31 ms, 内存: 16.2 MB


/*
 * 思路:
 * 1. 使用 Java Stream 来简化代码逻辑。
 * 2. 仍然使用 isStretchy 函数判断每个查询单词是否可扩展。
 */

import java.util.stream.Stream;

public class ExpressiveWordsStream {
    public static void main(String[] args) {
        String s = "heeellooo";
        String[] words = {"hello", "hi", "helo"};
        System.out.println(expressiveWords(s, words)); // 输出: 1
    }

    public static long expressiveWords(String s, String[] words) {
        return Stream.of(words).filter(word -> isStretchy(s, word)).count();
    }

    public static boolean isStretchy(String s, String word) {
        int i = 0, j = 0;
        while (i < s.length() && j < word.length()) {
            if (s.charAt(i) != word.charAt(j)) return false;
            int lenS = getRepeatedLength(s, i);
            int lenW = getRepeatedLength(word, j);
            if (lenS < 3 && lenS != lenW || lenS >= 3 && lenS < lenW) return false;
            i += lenS;
            j += lenW;
        }
        return i == s.length() && j == word.length();
    }

    private static int getRepeatedLength(String s, int index) {
        int length = 0;
        char c = s.charAt(index);
        while (index + length < s.length() && s.charAt(index + length) == c) {
            length++;
        }
        return length;
    }
}

解释

方法:

该题解的核心思路是首先将输入字符串S和比较的单词列表words中的每个单词分解成字母组的形式。字母组是指相邻的并且相同的字母序列。例如,'heeellooo' 会被分解为 ['h', 'eee', 'll', 'ooo']。分解后,对于每个单词,检查其分解形式是否可以通过扩展操作与S的分解形式匹配。扩展操作允许将一个字母组扩展到至少3个相同字符,前提是原始字母组至少有1个字符。题解通过遍历words列表中每个单词的字母组,逐个比较每个字母组的字符和长度,以判断是否可以通过扩展变为目标字母组。如果一个单词的所有字母组都能匹配,那么这个单词被认为是可扩张的。

时间复杂度:

O(n + m*k + m*l)

空间复杂度:

O(n + k)

代码细节讲解

🦆
在算法中,如何确保每个字母组的正确分割,避免例如 'aaa' 错误地分割成 ['a', 'aa']?
在算法中,确保字母组正确分割的关键在于使用一个循环来检查当前字符是否与上一个字符相同。如果相同,则将当前字符添加到当前字母组中;如果不同,则开始一个新的字母组。这种方法可以确保如 'aaa' 被正确分割为 ['aaa'] 而不是 ['a', 'aa']。在题解中,这一逻辑通过检查是否有前一个元素以及前一个元素的字符是否与当前字符相同来实现。
🦆
题解中提到的 '扩张操作允许将一个字母组扩展到至少3个相同字符,前提是原始字母组至少有1个字符',这是否意味着原字符串S中的字母组长度必须比words中相应的字母组长才能进行扩展?
是的,根据题解的逻辑,要进行扩展操作,S中的字母组不仅需要比word中的相应字母组长,并且S中的字母组长度必须至少为3或者更多。这确保了只有当S中的字母组足够长时,才能通过添加相同字符来进行有效的扩展。如果word中的某个字母组比S中的相应字母组长,或者S中的字母组长度少于3而word中的字母组长度为3或更多,则这种扩展是不可能的。
🦆
在比较两个字母组时,题解考虑了字母组的字符和长度,但如果两个字母组的长度相同,字符相同,却不满足扩展条件(例如长度小于3),这种情况如何处理?
在这种情况下,如果两个字母组的长度相同且字符相同,但长度小于3,这意味着无法进行扩展操作,但这并不影响两个字母组的匹配性。只要字符和长度都相同,就认为这两个字母组是匹配的。因此,在题解中,这种情况下仍然会视两个字母组为相匹配,不需要额外的处理。

相关问题