共计 1306 个字符，预计需要花费 4 分钟才能阅读完成。
题目
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.
题目地址
讲解
这道题我居然一遍过，以前做题或多或少有些小错误。这道题我一上手就发现应该尽量阻止对数据的多次遍历，所以如果能遍历一遍得到一些有用的信息就好了。我用的解法是，建立一个 map 存储每个字母的首尾位置（当然实际操作中我用的是两个 map 分别存储字母第一次出现的位置和最后一次出现的位置）。然后如果这一段之间出现了一个字母，它的尾部位置比框住它的这个字母更大，就更新尾部位置，直到尾部位置无法再扩大为止。
Java 代码
class Solution {
public List<Integer> partitionLabels(String S) {
List<Integer> result = new ArrayList<>();
char[] c = S.toCharArray();
Map<Character, Integer> mapStart = new HashMap<>();
Map<Character, Integer> mapEnd = new HashMap<>();
for(int i=0;i<c.length;i++){
if(mapStart.get(c[i])==null){
mapStart.put(c[i], i);
mapEnd.put(c[i], i);
}else{
mapEnd.put(c[i], i);
}
}
int beginIndex=0;
while(beginIndex<c.length){
int endIndex=mapEnd.get(c[beginIndex]);
for(int i=beginIndex;i<endIndex;i++){
if(mapEnd.get(c[i])>endIndex){
endIndex = mapEnd.get(c[i]);
}
}
result.add(endIndex-beginIndex+1);
beginIndex = endIndex+1;
}
return result;
}
}
