[LeetCode]Partition Labels

题目描述:

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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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

Pingbacks已关闭。

暂无评论

张贴您的评论