【一天一大 lee】划分字母区间 (难度:中等) - Day20201022
【一天一大 lee】划分字母区间 (难度:中等) - Day20201022
前端小书童
发布于 2020-11-03 10:12:55
发布于 2020-11-03 10:12:55
20201022
题目:
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。
示例：
- 示例 1：
输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
提示：
- S 的长度在[1, 500]之间。
- S 只包含小写字母 'a' 到 'z' 。
抛砖引玉
思路：
思路
'a' => 8,
'b' => 5,
'c' => 7,
'd' => 14,
'e' => 15,
'f' => 11,
'g' => 13,
'h' => 19,
'i' => 22,
'j' => 23,
'k' => 20,
'l' => 21
先找到每个字符最后出现的位置，然后逐个查询字符，
在找到元素最后位置之前遇到最后位置更靠后的字符则扩展需要截取的长度，
直到截取到当前判断所有字符最后出现的位置都在当前片段内
抛砖引玉
/**
* @param {string} S
* @return {number[]}
*/
var partitionLabels = function(S) {
let map = new Map(),
_result = [],
index = 0,
maxIndex = 0
for (let i = 0; i < S.length; i++) {
map.set(S[i], i)
}
let i = 0
while (i < S.length) {
maxIndex = Math.max(map.get(S[i]), maxIndex)
if (i == maxIndex) {
_result.push(i - index + 1)
index = i + 1
}
i++
}
return _result
}
博客: 前端小书童
每天的每日一题，写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言
公众号：前端小书童
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-10-22，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录