LeetCode-热题100：763. 划分字母区间

题目描述

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：
输入： s = “ababcbacadefegdehijhklij”
输出： [9,7,8]
解释：
划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的，因为划分的片段数较少。

示例 2：

输入： s = “eccbbbbdec”
输出： [10]

提示：

• 1 <= s.length <= 500
• s 仅由小写英文字母组成

代码及注释

func partitionLabels(s string) []int {// 创建一个数组来存储每个字符最后出现的位置lastPos := make([]int, 26)// 结果数组，用于存储每个分区的长度res := make([]int, 0)// 遍历字符串，记录每个字符最后出现的位置for i, c := range s {lastPos[c - 'a'] = i}// 初始化分区的开始和结束位置start, end := 0, 0// 再次遍历字符串来确定分区for i, c := range s {// 更新当前分区的结束位置为当前字符的最后出现位置end = max(end, lastPos[c - 'a'])// 如果当前位置i等于当前分区的结束位置，说明找到了一个分区if i == end {// 计算当前分区的长度并添加到结果数组中res = append(res, end - start + 1)// 更新下一个分区的开始位置start = end + 1}}// 返回结果数组return res
}// 返回两个数的最大值
func max(a, b int) int {if a > b {return a}return b
}

代码解释

1. 记录每个字符的最后出现位置：

   for i, c := range s {lastPos[c - 'a'] = i
   }
   

   这里我们遍历字符串s并记录每个字符最后出现的位置。这样，当我们遍历字符串以确定子串边界时，我们可以直接查找每个字符的最后出现位置。

2. 确定子串的边界：

   for i, c := range s {end = max(end, lastPos[c - 'a'])if i == end {res = append(res, end - start + 1)start = end + 1}
   }
   

   在这个循环中，我们遍历字符串s。对于每个字符，我们更新当前子串的结束位置end为当前字符的最后出现位置。当i == end时，意味着我们找到了一个子串，其边界是start到end。我们计算这个子串的长度并将其添加到结果数组res中，然后更新start为end + 1以寻找下一个子串。

3. 返回结果数组：

   return res
   

   最后，我们返回结果数组res，其中包含了所有子串的长度。

通过这种方法，我们可以有效地找到字符串s中所有满足条件的子串，其中每个字母只出现在一个子串中。