题目描述:
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。
注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1:
输入:s = “ababcbacadefegdehijhklij”
输出:[9,7,8]
解释:
划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的,因为划分的片段数较少。
示例 2:
输入:s = “eccbbbbdec”
输出:[10]
提示:
1 <= s.length <= 500
s 仅由小写英文字母组成
解题思路一:Python贪心
可以分为如下两步:
- 统计每一个字符最后出现的位置
- 从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前下标相等了,则找到了分割点
class Solution:
def partitionLabels(self, s: str) -> List[int]:
last_occurrence = {} # 存储每个字符最后出现的位置
for i, ch in enumerate(s):
last_occurrence[ch] = i
result = []
start = 0
end = 0
for i, ch in enumerate(s):
end = max(end, last_occurrence[ch]) # 找到当前字符出现的最远位置
if i == end: # 如果当前位置是最远位置,表示可以分割出一个区间
result.append(end - start + 1)
start = i + 1
return result
时间复杂度:O(n)
空间复杂度:O(1)
解题思路二:Python贪心2
class Solution:
def partitionLabels(self, s: str) -> List[int]:
last = {}
for i, ch in enumerate(s):
last[ch] = i
ans = []
start = 0
end = 0
for i, ch in enumerate(s):
end = max(end, last[ch])
if i == end:
ans.append(end - start + 1)
start = i + 1
return ans
时间复杂度:O(n)
空间复杂度:O(1)文章来源:https://www.toymoban.com/news/detail-846936.html
解题思路三:0
时间复杂度:O(n)
空间复杂度:O(n)文章来源地址https://www.toymoban.com/news/detail-846936.html
到了这里,关于LeetCode-763. 划分字母区间【贪心 哈希表 双指针 字符串】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!