情感丰富的文字
难度:
标签:
题目描述
代码结果
运行时间: 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']?
▷🦆
题解中提到的 '扩张操作允许将一个字母组扩展到至少3个相同字符,前提是原始字母组至少有1个字符',这是否意味着原字符串S中的字母组长度必须比words中相应的字母组长才能进行扩展?
▷🦆
在比较两个字母组时,题解考虑了字母组的字符和长度,但如果两个字母组的长度相同,字符相同,却不满足扩展条件(例如长度小于3),这种情况如何处理?
▷