题目地址：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 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发