共计 1136 个字符，预计需要花费 3 分钟才能阅读完成。
写在前面
今天这篇文章是贪心算法系列的第三篇 – 划分字母区间。
前文回顾：
【LeetCode】贪心算法 – 分发糖果（135）
刷题汇总：
【LeetCode】汇总贴（NO.1-20）
今日题目
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。
示例 1: 输入: S = “ababcbacadefegdehijhklij” 输出: [9,7,8]解释: 划分结果为 “ababcbaca”, “defegde”, “hijhklij”。每个字母最多出现在一个片段中。像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。
注意:S 的长度在 [1, 500] 之间。S 只包含小写字母 ’a’ 到 ’z’。
题目分析
解决此题关键就是找到能分割的条件，对 S 的每个字符进行判断，看是否此字符是被分割到另一个字符中，从题目中得到每个字母最多出现在一个片段中，那么从第一个字符开始，它的最后一个相同的字符一定在这个片段中，得到第一个条件：
当此字符在前面分割中出现，就不能当做分割点
只有这个条件就可以了吗？我们再考虑一下，当前字符并没有在前面分割的区间中出现，是不是能直接作为分割点呢？以下面的字符串为例进行分割。
“aaaaab cdaefgh”当判断 b 的时候，先在前面已经分好的字符串 aaaaa 里面没有，符合找到的第一个条件，如果我们把 b 当做新的分割点，很明显是错误的，因为在 b 后面的字符串里，又一次出现了 a，当我们以 b 作为分割点是不符合条件的，因此得到第二个限制条件：分割点后面不能出现前面一个字符串中的字符。
进行了上面的分析但是可以用 python 做个弊, 使用 rindex()方法，从第一个字符开始，假设位置为 a，用 rindex 方法找到最后一次出现的位置 b，那么这个区间就为[a,b]。之后每个字符都找最后一个位置，如果在区间之外则扩大区间，如果遍历到区间的最后一个位置，则结束，长度就为结束位置减开始位置加 1。
代码实现
class Solution:
def partitionLabels(self, S):
“””
:type S: str
:rtype: List[int]
“””
i = 0
res = []
while i < len(S):
start = i
end = S.rindex(S[i])
for j in range(i,len(S)):
last = S.rindex(S[j])
if last > end:
end = last
elif j == end:
res.append(end-start + 1)
i = end + 1
break
return res
推荐阅读：
python 异常报错详解
机器学习实战 – 住房月租金预测（3）
机器学习实战 – 住房月租金预测（2）