字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。
示例 1:
输入: S = "ababcbacadefegdehijhklij"
输出: [9,7,8]
解释:
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
注意:
S的长度在[1, 500]之间。
S只包含小写字母'a'到'z'。
看到这道题目确实有点懵逼，不知道从何下手，但是还好有个示例。
观察划分结果1的字符串，发现首字符和最后一个字符相等，猜想划分的依据是遍历整个字符串，第一个字符第一次出现的位置和最后出现的位置，把它们和之间的字符串划分出来，后来再依次划分。
再观察第二个字符串，发现结果不对，进行修正。这个字符串的结尾不是‘d’，而是‘e’。因为同一个字母只会出现在一个片段，所以根据之前得到的划分结果划分出来的字符串，还要对里面的字符进行遍历，找到里面这个字符最后出现的位置的最大值，用这个最大值来作为划分字符串的结尾。
class Solution {
public List<Integer> partitionLabels(String S) {
List<Integer> list = new ArrayList<>();
for(int i = 0; i < S.length(); i++) {
//遍历字符,找到字符最后出现的位置
int last = S.lastIndexOf(S.charAt(i));
int max = last;
for(int j = i; j <= max; j++) {
//遍历字符和最后出现位置之间的字符,找到最后出现位置的最大值,用这个最大值更新遍历范围
max = Math.max(max, S.lastIndexOf(S.charAt(j)));
if(max == S.length()-1) {
break;
}
}
//终点减起点加1就是范围
list.add(max - i +1);
//i更新到遍历到的字符串末尾,整个过程看起来用了双重循环,但是只是对整个字符串遍历了一次
i = max;
}
return list;
}
}
但是这个解法耗时很长,分析了一下,是因为在找字符最后一次出现位置时调用的lastIndexOf会遍历字符串,所以我们声明一个新数组来存储每一个字符最后出现的位置,这样找到最后位置就不用了遍历字符串.
class Solution {
public List<Integer> partitionLabels(String S) {
List<Integer> list = new ArrayList<>();
int[] last = new int[26];
//用一个数组来存储每一个字符出现的最后位置
for(int i = 0; i < S.length(); i++) {
last[S.charAt(i) - 'a'] = i;
}
//把字符串变成字符数组遍历
char[] chars = S.toCharArray();
for(int i = 0; i < chars.length; i++) {
int max = last[chars[i] - 'a'];
//注意这里遍历的范围是要变动的
for(int j = i; j <= max; j++) {
max = Math.max(max, last[chars[j] - 'a']);
if(max == chars.length-1) {
break;
}
}
list.add(max - i +1);
i = max;
}
return list;
}
}