统计同质子字符串的数目
难度:
标签:
题目描述
代码结果
运行时间: 67 ms, 内存: 16.3 MB
/*
* 题目思路:
* 使用 Java Stream API 处理字符串的同质子字符串计数问题。
* 由于需要对每个字符进行遍历和分组,我们可以使用 Streams 和 Collectors 来实现。
* 统计每个字符的连续段的长度,并计算每段的同质子字符串数量。
*/
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Solution {
public int countHomogenous(String s) {
long MOD = 1000000007;
long count = IntStream.range(0, s.length())
.filter(i -> i == 0 || s.charAt(i) != s.charAt(i - 1))
.mapToObj(i -> {
int j = i;
while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;
long len = j - i;
return len * (len + 1) / 2;
})
.collect(Collectors.summingLong(Long::longValue));
return (int) (count % MOD);
}
}
解释
方法:
该题解采用了一次遍历的方法来统计同质子字符串的数量。它通过维护一个计数器 c 来记录当前同质子字符串的长度,当遇到与上一个字符不同的字符时,就计算以前一个字符为结尾的所有同质子字符串的数量,并将计数器 c 重置为 1。该方法利用了等差数列求和公式来快速计算同质子字符串的数量。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
题解中提到使用计数器c来记录当前同质子字符串的长度,那么在遇到新字符时,具体是如何处理当前记录的同质子字符串的计数的?
▷🦆
在题解的代码中,为什么在每次字符变更时,需要使用等差数列求和公式`(c + 1) * c / 2`来计算同质子字符串的数量?
▷🦆
题解中提到最后需要对最终的同质子字符串总数进行取余操作,这样的操作有什么特定的目的吗?
▷🦆
如果输入字符串s为空怎样处理?题解中有没有对这种边界情况进行处理?
▷