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()总结划分字母区间是贪心算法的典型应用通过统计每个字符最后一次出现的位置来划分片段。