0763._Partition_Labels.md

763. Partition Labels

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/partition-labels/description/

内容描述

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:

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

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

从第一个字母开始，只要我们包含了这个字母，那么它在S中出现的最后一次我们也要包含进去，当前出现过的所有的字母，我们每次都要更新最后出现的那一次， 并且要一直遍历到其最后一次，这样我们可以维护一个当前至少需要遍历到的end，然后只要出现一个新的字母， 就更新一个这个end（取新字母最后出现idx和end之间的大者），最后，当我们遍历到一个idx的时候，如果这个idx与我们的end相等， 说明截止当前所有出现的字母都在我们的[start, end]字串当中了，直接append它的长度到res中，一直遍历到最后，返回res

beats 98.39%

class Solution(object):
    def partitionLabels(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        if not S or len(S) == 0:
            return True
        lookup = {}
        for i, c in enumerate(S):
            lookup[c] = i
        start, end, res = 0, 0, []
        for i, c in enumerate(S):
            end = max(end, lookup[c])
            if i == end:
                res.append(end-start+1)
                start = i + 1
        return res