Leetcode 1180:统计只含单一字母的子串(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1180:统计只含单一字母的子串(超详细的解法!!!)

in leetcode with 0 comment

给你一个字符串 S,返回只含 单一字母 的子串个数。

示例 1:

输入: "aaaba"
输出: 8
解释: 
只含单一字母的子串分别是 "aaa", "aa", "a", "b"。
"aaa" 出现 1 次。
"aa" 出现 2 次。
"a" 出现 4 次。
"b" 出现 1 次。
所以答案是 1 + 2 + 4 + 1 = 8。

示例 2:

输入: "aaaaaaaaaa"
输出: 55 

提示:

  1. 1 <= S.length <= 1000
  2. S[i] 仅由小写英文字母组成。

解题思路

这是一个找规律的问题,规律很简单,就是统计字符串中连续相同字符的个数,如"aaaba"的输出是311。接着对每个数采用等差数列求和即可,(1+3)*3//2 + (1+1)*1//2+(1+1)*1//2=8

class Solution:
    def countLetters(self, S: str) -> int:
        res = 0
        for _, j in itertools.groupby(S):
            t = len(list(j))
            res += (1 + t)*t//2
        return res

更加简洁的写法

class Solution:
    def countLetters(self, S: str) -> int:
        return sum([sum(range(1, len(list(j)) + 1)) for i , j in itertools.groupby(S)])

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses