划分字母区间
# 📃 题目描述
题目链接:763. 划分字母区间 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例:
输入:S = "ababcbacadefegdehijhklij"
输出:[9,7,8]
解释:
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的,因为划分的片段数较少。
# 🔔 解题思路
以 ababcbacadefegdehijhklij 举例
- 第 1 个字符 a 加入第一个片段,这是确定的,然后找到 a 出现的最后一个位置,这之间的所有字符都加入第一个片段,若最后一个 a 的后面还存在第一个片段内的字符,则一并加入。所以,第一个区间就是 ababcbaca
- 同样的,紧接着第一个区间之后,将 d 加入第二个区间,然后找到 d 出现的最后一个位置,这之间的所有字符都加入第二个片段,若最后一个 d 的后面还存在第二个片段内的字符,则一并加入。所以,第二个区间就是 defegde
- .....
具体该怎么用代码表示呢?
一句话:如果找到之前遍历过的所有字母的最远边界,说明这个边界就是分割点了
可以分为如下两步:
- 统计每一个字符最后出现的位置
- ⭐ 从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前遍历到的下标 i 相等了,则说明找到了分割点
class Solution {
public List<Integer> partitionLabels(String s) {
// 记录每个字符的最远边界, 总共只有 26 个字符,可以使用数组代替哈希表
int edge[] = new int[26];
for (int i = 0; i < s.length(); i ++) {
edge[s.charAt(i) - 'a'] = i;
}
// 记录每个片段的长度
List<Integer> res = new ArrayList<>();
// 记录字符的最远边界
int max_edge = 0;
// 记录每个片段的起始下标
int start = 0;
for (int i = 0; i < s.length(); i ++) {
// 更新最远边界
max_edge = Math.max(max_edge, edge[s.charAt(i) - 'a']);
if (i == max_edge) {
res.add(i - start + 1);
// 下一个片段的起始位置
start = i + 1;
}
}
return res;
}
}
# 💥 复杂度分析
- 空间复杂度:O(N)
- 时间复杂度:O(N)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10