题目
763. 划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 “ababcc” 能够被分为 [“abab”, “cc”]，但类似 [“aba”, “bcc”] 或 [“ab”, “ab”, “cc”] 的划分是非法的。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：s = “ababcbacadefegdehijhklij”
输出：[9,7,8]
解释：
划分结果为 “ababcbaca”、”defegde”、”hijhklij” 。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的，因为划分的片段数较少。
示例 2：
输入：s = “eccbbbbdec”
输出：[10]
提示：
- 1 <= s.length <= 500
- s 仅由小写英文字母组成
我的代码（TypeScript）
function partitionLabels(s: string): number[] {
let cntArray: number[][] = Array.from({ length: 26 }, () => [-1, -1]);
for (let i: number = 0; i < s.length; i++) {
const idx: number = s[i].charCodeAt(0) - 97;
if (cntArray[idx][0] == -1) {
cntArray[idx][0] = i;
}
cntArray[idx][1] = i;
}
cntArray.sort((a, b) => a[0] - b[0]);
let result: number[][] = [];
for (let i = 0; i < 26; i++) {
if (cntArray[i][0] == -1) {
continue;
}
let combined: Boolean = false;
for (let j: number = 0; j < result.length; j++) {
if (cntArray[i][1] > result[j][0] && cntArray[i][0] < result[j][1]) {
result[j][0] = Math.min(cntArray[i][0], result[j][0]);
result[j][1] = Math.max(cntArray[i][1], result[j][1]);
combined = true;
break;
}
}
if (!combined) {
result.push(cntArray[i]);
}
}
return result.sort((a, b) => a[0] - b[0]).map(r => r[1] - r[0] + 1);
};点评
思路是找出各个字母的起始和结束索引，然后把有重叠的进行合并。
合并这里用了直接遍历，不确定有没有更简单的方法。
效率不算很好。
官方的贪心算法需要遍历字符串两次，
我只遍历一次，所以如果字符串很长，可能我的方法会好一点。
不过这里长度只有500，所以相比来说效率不算好。
另外我的算法还处理了起始位置，这一点似乎有些多余。
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog