一开始,很容易想到用双指针去定位两个相同字符的最远区间,然后使用重叠区间合并的思维去得到最终片段。大方向双指针思路是对的,不过没有优化,所以复杂度较高,但能AC
class Solution {
public:
vector<int> partitionLabels(string S) {
if (S.empty()) return {};
int size = S.size();
vector<int> solution;
vector<bool> used(size, false);
int len = 0;
for (int i = 0, first = 0, end = size - 1; i <= end; end--) {
// 右指针只需要遍历到已确定区间外
if (used[end]) {
i++;
end = size;
continue;
} // 若i走到片段边界,则添加该片段,并重置片段长度为0
if (len && i >= first + len) {
solution.emplace_back(len);
first = i;
len = 0;
}
// 合并区间
if (!used[i] && S[i] == S[end]) {
used[end] = true;
len = max(len, end - first + 1);
i++; end = size;
}// 段尾处理
if (len + first == size) {
solution.emplace_back(len);
break;
}
}
return solution;
}
};
本题的本质反倒不是题目所说的划分区间,而是变相合并重叠区间
,只不过需要借助合适的数据结构实现
class Solution {
public:
vector<int> partitionLabels(string S) {
int hash[26] = {0};
int size = S.size();
vector<int> solution;
// 1.构建最大字母索引哈希表
for (int i = 0; i < size; i++)
hash[S[i] - 'a'] = i;
// 双指针包含片段
int first = 0, end = 0;
for (int i = 0; i < size; i++) {
// 2.探索重叠区间,如果有则合并
end = max(end, hash[S[i] - 'a']);
if (i == end) { // 到达区间右边界则片段符合条件,添加到最终结果中
solution.emplace_back(end - first + 1);
first = i + 1;
}
}
return solution;
}
};
时间复杂度在哈希表的助力下大大下降
图片来源于「代码随想录」公众号,欢迎大家关注这位大佬的公号