力扣763-划分字母区间

763. 划分字母区间 - 力扣LeetCode给你一个字符串s。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。例如字符串ababcc能够被分为[abab, cc]但类似[aba, bcc]或[ab, ab, cc]的划分是非法的。注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是s。返回一个表示每个字符串片段的长度的列表。示例 1输入s ababcbacadefegdehijhklij输出[9,7,8]解释划分结果为 ababcbaca、defegde、hijhklij 。每个字母最多出现在一个片段中。像 ababcbacadefegde, hijhklij 这样的划分是错误的因为划分的片段数较少。示例 2输入s eccbbbbdec输出[10]提示1 s.length 500s仅由小写英文字母组成统计每个字符出现的区间即可以示例一为例s ababcbacadefegdehijhklij字母下标下标区间a0,2,6,8[0,8]b1,3,5[1,5]c4,7[4,7]d9,14[9,14]e10,12,15[10,15]f11[11,11]g13[13,13]h16,19[16,19]i17,22[17,22]j18,23[18,23]k20[20,20]l21[21,21]例如 d 的区间是[9, 14]区间有重叠的字母为 e f g将这四个区间取并集就是[9, 15]类似地表中的区间可以合并为[0, 8], [9, 15],[16, 23]方法1.遍历 s求出字母 c 在 s 中最后出现的下标last[c]2.初始化当前正在合并的区间的左右端点 start 与 end 为 03.遍历 s因为当前区间应当包含所有s[i]因此用last[s[i]]更新 end 的最大值4.如果 i 等于 end那么说明成功合并区间将 end - start 1 放入答案数组中5.令 start end 1接着开始下一轮合并class Solution: def partitionLabels(self, s: str) - List[int]: last {c : i for i, c in enumerate(s)} ans [] start end 0 for i, c in enumerate(s) : end max(end, last[s[i]]) if end i : ans.append(end - start 1) start end 1 return ans