题目地址:https://leetcode.com/problems/partition-labels/description/

题目描述

Astring 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、 Swillhavelengthinrange[1,500].;
2、 Swillconsistoflowercaseletters('a'to'z')only.;

解题方法

方法一:

题意是要对一个字符串进行尽可能多的划分,并保证每个划分中的元素不在其他划分中出现。

想法比较具有技巧性。如果一段序列中每个元素的在S中最右边的序号都在某个范围内,那么就可以划分成一个段。

因此,使用字典保存每个元素出现的最靠右的位置。然后对字符串S进行遍历,找出最靠右的序号的最大值j。如果i和j重合了,说明已经到了这个划分的末尾了,然后进行划分。并开始计算下一个划分。

class Solution(object):
    def partitionLabels(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        lindex = {c: i for i, c in enumerate(S)}
        j = anchor = 0
        ans = []
        for i, c in enumerate(S):
            j = max(j, lindex[c])
            if i == j:
                ans.append(j - anchor + 1)
                anchor = j + 1
        return ans

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

C++版本如下:

class Solution {
public:
    vector<int> partitionLabels(string S) {
        map<char, int> d;
        for (int i = 0; i < S.size(); i++) d[S[i]] = i;
        int start = 0, end = 0;
        vector<int> res;
        for (int i = 0; i < S.size(); i++) {
            end = max(end, d[S[i]]);
            if (i == end) {
                res.push_back(end - start + 1);
                start = end + 1;
            }
        }
        return res;
    }
};

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发