LeetCode 划分字母区间题解

LeetCode 划分字母区间题解

题目描述

给定一个字符串 S，将它划分成尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个片段的长度的列表。

示例：

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]

解题思路

方法：贪心

思路：

• 首先统计每个字符最后一次出现的位置。
• 然后遍历字符串，维护当前片段的结束位置。
• 当当前位置达到当前片段的结束位置时，将片段长度加入结果列表。

复杂度分析：

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

代码实现

def partition_labels(s): last = {c: i for i, c in enumerate(s)} result = [] start = 0 end = 0 for i, c in enumerate(s): end = max(end, last[c]) if i == end: result.append(end - start + 1) start = end + 1 return result # 测试 def test_partition_labels(): s = "ababcbacadefegdehijhklij" print(partition_labels(s)) # 输出：[9, 7, 8] if __name__ == "__main__": test_partition_labels()

总结

划分字母区间是贪心算法的典型应用，通过统计每个字符最后一次出现的位置来划分片段。