题目描述：

LeetCode 763. Partition Labels

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

Note:

1. S will have length in range [1, 500].
2. S will consist of lowercase letters ('a' to 'z') only.

题目大意：

将字符串S拆分成首位相接的几个部分，确保每个部分的字母不在别的部分出现。求满足条件并且拆分个数最多的方案。

解题思路：

由于S只包含字母a - z，因此按照字母统计出现的最小、最大位置。

将得到的位置范围列表rangeList按照起点从小到大、终点从大到小的规则排序。

记当前区间的起点、终点为cmin, cmax，初始均为0

遍历rangeList，记当前起点、终点分别为start，end

若start > cmax，说明上一区间可以封闭，将上一区间加入答案，并更新cmin为start，cmax为end

否则，扩展cmax为max(cmax, end)

Python代码：

class Solution(object):
    def partitionLabels(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        rangeDict = {}
        for i, c in enumerate(S):
            if c not in rangeDict: rangeDict[c] = [i, i]
            else: rangeDict[c][1] = i
        rangeList = sorted(rangeDict.values(), cmp = lambda x, y: x[0] - y[0] or y[1] - x[1])
        ans = []
        cmin = cmax = 0
        for start, end in rangeList:
            if start > cmax:
                ans.append(cmax - cmin + 1)
                cmin, cmax = start, end
            else: cmax = max(cmax, end)
        ans.append(cmax - cmin + 1)
        return ans

 

本文链接：http://bookshadow.com/weblog/2018/01/14/leetcode-partition-labels/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码