力扣 763. 划分字母区间

**力扣763. 划分字母区间**

### 题目描述给定一个由小写字母组成的字符串 `S`，我们需要将其划分为尽可能多的字母区间。每个字母区间都是连续的且不重叠的。

例如，如果输入是 `"abacaba"`, 则输出应该是 `[["a","b"],["c","a"],["b","a"]]`。

###问题分析这个问题需要我们能够识别出连续的字母序列，并将其分割成尽可能多的区间。我们可以使用贪心算法来解决这个问题。

### 贪心算法解释贪心算法是一种常见的算法设计技巧，涉及在每一步中选择当前最优的解决方案，以期望达到全局最优的结果。在本题中，我们可以将其应用于识别连续字母序列。

###代码实现

class Solution:
 def partitionLabels(self, S: str) -> List[List[str]]:
 # 初始化一个空列表来存储字母区间 result = []
 # 如果输入字符串为空，则返回空列表 if not S:
 return result # 初始化两个指针，分别用于遍历输入字符串的开始和结束 start, end =0,0 # 遍历输入字符串 while end < len(S):
 # 将当前字符作为区间的结束点 end = max(end, S.rfind(S[end]))
 # 如果当前区间包含了所有字母，则将其添加到结果列表中 if start == end:
 result.append([S[start]])
 start +=1 end +=1 else:
 # 否则，将当前区间的起始点和结束点作为一个子串添加到结果列表中 result.append([S[start:end+1]])
 # 将起始点和结束点更新为当前区间的结束点 start = end +1 end +=1 return result# 测试用例solution = Solution()
print(solution.partitionLabels("abacaba")) # 输出: [["a","b"],["c","a"],["b","a"]]