leetcode 830. 较大分组的位置

旧城等待， 2022-04-17 06:59 107阅读 0赞

**近期一直在用python刷leetcode的题，代码都提交到了github上了：[https://github.com/Teingi/test][https_github.com_Teingi_test]**

在一个由小写字母构成的字符串 `S` 中，包含由一些连续的相同字符所构成的分组。

例如，在字符串 `S = "abbxxxxzyy"` 中，就含有 `"a"`, `"bb"`, `"xxxx"`, `"z"` 和 `"yy"` 这样的一些分组。

我们称所有包含大于或等于三个连续字符的分组为较大分组。找到每一个较大分组的起始和终止位置。

最终结果按照字典顺序输出。

**示例 1:**

输入: "abbxxxxzzy"
    输出: [[3,6]]
    解释: "xxxx" 是一个起始于 3 且终止于 6 的较大分组。

**示例 2:**

输入: "abc"
    输出: []
    解释: "a","b" 和 "c" 均不是符合要求的较大分组。

**示例 3:**

输入: "abcdddeeeeaabbbcd"
    输出: [[3,5],[6,9],[12,14]]

**说明: ** `1 <= S.length <= 1000`

**思路：**

1、设置两个指针i,j。并初始化i = 0,j = 1;当S\[i\] = S\[j\]相等的时候，j往后移动一位，i不动。当S\[j\] != S\[i\]时，首先判断j>i+3没有，如果没有就不用记录这组结果，如果大于就记录；记录完成后再移动i,j，此时，i应该移动到j的位置，j应该移动到j+1的位置。

**问题：**

按思路1进行遍历的话，有一种情况是执行不到j>i+3这个语句。这种情况就是：S = fyghllkjlaaa(序列的后几位满足条件)

改进：

在S序列后边加上一个' '(空格)，摆脱这种情况就可以安心用思路一解题。

class Solution(object):
        def largeGroupPositions(self, S):
            """
            :type S: str
            :rtype: List[List[int]]
            """
            if len(S) < 3:
                return []
            
            #对S字符串进行变换，添加一个空格
            S = S + ' '
            raw = []
            i,j = 0,1
            while (i < j) and (j < len(S)):
                if S[i] == S[j]:
                    j += 1                
                else:
                    if j >= i + 3:
                        raw.append([i,j-1])
                    i = j
                    j += 1
            return raw

[https_github.com_Teingi_test]: https://github.com/Teingi/test