目录

一、题目内容

二、解题思路

三、代码

一、题目内容

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

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

分组可以用区间 [start, end] 表示，其中 start 和 end 分别表示该分组的起始和终止位置的下标。上例中的 "xxxx" 分组用区间表示为 [3,6] 。

我们称所有包含大于或等于三个连续字符的分组为 较大分组 。

找到每一个 较大分组 的区间，按起始位置下标递增顺序排序后，返回结果。

示例 1：

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

示例 2：

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

示例 3：

输入：s = "abcdddeeeeaabbbcd"
输出：[[3,5],[6,9],[12,14]]
解释：较大分组为 "ddd", "eeee" 和 "bbb"

示例 4：

输入：s = "aba"
输出：[]

二、解题思路

利用字典存储每个字母连续的区间，其中每个字母对应的value值的第一个元素作为是否是当前字母的标志，结果集里存储长度为3的区间即可。

三、代码

  

   

    

     

    
    

     

      class Solution:
     
    
   

    

     

    
    

     
 def largeGroupPositions(self, s: str) -> list:
     
    
   

    

     

    
    

     

       s_dict = {}
     
    
   

    

     

    
    

     
 for i in range(len(s)):
     
    
   

    

     

    
    

     
 if i != 0:
     
    
   

    

     

    
    

     
 if s[i] != s[i - 1]:
     
    
   

    

     

    
    

     

       s_dict[s[i - 1]][0] = 0
     
    
   

    

     

    
    

     
 if len(s_dict[s[i - 1]][-1]) != 2:
     
    
   

    

     

    
    

     

       s_dict[s[i - 1]][-1].pop()
     
    
   

    

     

    
    

     
 if s[i] not in s_dict:
     
    
   

    

     

    
    

     

       s_dict[s[i]] = [1, [i]]
     
    
   

    

     

    
    

     
 else:
     
    
   

    

     

    
    

     
 if len(s_dict[s[i]][-1]) >= 2:
     
    
   

    

     

    
    

     
 if s_dict[s[i]][0] != 0:
     
    
   

    

     

    
    

     

       s_dict[s[i]][-1].pop(-1)
     
    
   

    

     

    
    

     

       s_dict[s[i]][-1].append(i)
     
    
   

    

     

    
    

     
 else:
     
    
   

    

     

    
    

     

       s_dict[s[i]].append([i])
     
    
   

    

     

    
    

     
 else:
     
    
   

    

     

    
    

     

       s_dict[s[i]][-1].append(i)
     
    
   

    

     

    
    

     

       s_dict[s[i]][0] = 1
     
    
   

    

     

    
    

     
 # print(s_dict)
     
    
   

    

     

    
    

     

       res = []
     
    
   

    

     

    
    

     
 for k, v in s_dict.items():
     
    
   

    

     

    
    

     
 for j in range(1, len(v)):
     
    
   

    

     

    
    

     
 if len(v[j]) == 2:
     
    
   

    

     

    
    

     
 if v[j][1] - v[j][0] >= 2:
     
    
   

    

     

    
    

     

       res.append([v[j][0], v[j][1]])
     
    
   

    

     

    
    

     

       sorted_res = sorted(res, key=lambda x: x[0])
     
    
   

    

     

    
    

     
 return sorted_res
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if __name__ == '__main__':
     
    
   

    

     

    
    

     

       s = "abcdddeeeeaabbbcd"
     
    
   

    

     

    
    

     

       ss = Solution()
     
    
   

    

     

    
    

     

       ans = ss.largeGroupPositions(s)
     
    
   

    

     

    
    

     

       print(ans)
     
    
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/112217737