題目
難度：★★☆☆☆
類(lèi)型：字符串
在一個(gè)由小寫(xiě)字母構(gòu)成的字符串 S 中恒序，包含由一些連續(xù)的相同字符所構(gòu)成的分組充甚。
例如音羞，在字符串 S = "abbxxxxzyy" 中钾唬，就含有 "a", "bb", "xxxx", "z" 和 "yy" 這樣的一些分組堰乔。
我們稱(chēng)所有包含大于或等于三個(gè)連續(xù)字符的分組為較大分組偏化。找到每一個(gè)較大分組的起始和終止位置。
最終結(jié)果按照字典順序輸出镐侯。
示例
示例 1
輸入: "abbxxxxzzy"
輸出: [[3,6]]
解釋: "xxxx" 是一個(gè)起始于 3 且終止于 6 的較大分組侦讨。
示例 2
輸入: "abc"
輸出: []
解釋: "a","b" 和 "c" 均不是符合要求的較大分組。
示例 3
輸入: "abcdddeeeeaabbbcd"
輸出: [[3,5],[6,9],[12,14]]
說(shuō)明: 1 <= S.length <= 1000
解答
較大分組：出現(xiàn)次數(shù)不小于3的連續(xù)字符串苟翻。我們可以通過(guò)一趟遍歷實(shí)現(xiàn)：
先判斷特殊情況韵卤，如果字符串的長(zhǎng)度小于3，那么一定不存在較大分組崇猫；
初始化變量：
（1）計(jì)數(shù)器count怜俐，表示到目前為止連續(xù)字符的數(shù)量；
（2）起始位置start邓尤，與當(dāng)前字符連續(xù)相同的最左側(cè)字符所在位置拍鲤；
（2）結(jié)果變列表res，用來(lái)存放最終結(jié)果汞扎；S的下標(biāo)i是從1開(kāi)始到len(S)-1的指針季稳，i+1指向i后一個(gè)元素，如果S[i+1]=S[i]澈魄，則計(jì)數(shù)器+1景鼠，否則，該組子串遍歷完畢痹扇，判斷計(jì)數(shù)器是否不小于3铛漓，如果不小于3，當(dāng)前組子串是較大分組鲫构，應(yīng)該將起止位置添加到結(jié)果列表中浓恶。
跳出循環(huán)后，還應(yīng)該判斷最后一個(gè)分組是否為較大分組结笨。
class Solution:
def largeGroupPositions(self, S):
if len(S) < 3:
return []
res = []
count = 1
start = 0
for i in range(1, len(S)):
if S[i] == S[i-1]:
count += 1
else:
if count >= 3:
res.append([start, start+count-1])
start, count = i, 1
if count >= 3:
res.append([start, start + count - 1])
return res
如有疑問(wèn)或建議包晰，歡迎評(píng)論區(qū)留言~
