## 题目
字符串 S
由小写字母组成。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例 1:
输入:S = "ababcbacadefegdehijhklij"
输出:[9,7,8]
解释:
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的,因为划分的片段数较少。
提示:
S
的长度在[1, 500]
之间。S
只包含小写字母'a'
到'z'
。
解题
方法一:贪心算法
思路
只有小写字母就可以使用数组代替哈希表,记录每个字符最后一次出现的位置。
遍历字符串维护当前片段的开始下标 start
和结束下标 end
,初始时 start = end = 0
。
遍历到的每一个字符都拿到其最后一次的出现位置 lasts[strArr[i] - 'a']
,则当前片段的结束下标一定不会小于该值,则 end = max(end, lasts[strArr[i] - 'a'])
。
当访问到下标 end
时,当前片段访问结束,当前片段的下标范围是 $[start, end]$ ,长度为 $start - end + 1$,然后令 start = end + 1
,继续寻找下一个片段。
代码
class Solution {
public List<Integer> partitionLabels(String s) {
char[] strArr = s.toCharArray();
int len = strArr.length;
int[] lasts = new int[26];
for (int i = 0; i < len; i++) {
lasts[strArr[i] - 'a'] = i;
}
List<Integer> ans = new ArrayList<>();
for (int i = 0, start = 0, end = 0; i < len; i++) {
end = Math.max(end, lasts[strArr[i] - 'a']);
if (i == end) {
ans.add(++end - start);
start = end;
}
}
return ans;
}
}
评论区