leetcode(力扣) 763. 划分字母区间

题目描述

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

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

思路分析

首先要记录出每一种字符最后的出现位置下标。像下面这样。

思路：从a开始遍历，a的最后一次出现的位置是8，如果从a到8这个位置之间的所有元素的最远位置都在8之内，则这就可以划分为一个区间。如果在这期间出现了比8大的最远距离，则更新最远距离。
比如下图第二个区间中的d最远距离为14，扫描到e的时候，最远距离更新为15.

算法过程：

• 初始化 变量，最远距离max_dis, 答案集合 and ，哈希表 hs。
• 使用哈希表 hs记录每一个字母最后出现的下标。
• 从头遍历字符串，如果 遍历下标 i == 最远距离max_dis了，那说明找到了一个区间，记录此时下标i。
• 在遍历的过程中，不断更新最远位置。
• 答案集只记录了区间的下标，题目要求返回每一区间长度，所以要再遍历一次求出来每一个区间的长度。

完整代码

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        hs = {}
        max_dis = 0
        res = []
        for i in range(len(s)):  # 哈希表
            hs[s[i]] = i
        print(hs)
        for i in range(len(s)):  # 划分区间，res记录每一个区间的末尾下标
            max_dis = max(max_dis,hs[s[i]])
            if i == max_dis:
                res.append(i)
        ans = []
        for i in range(len(res)-1,0,-1):  # 由区间末尾下标算出每个区间的长度。
            ans.append(res[i]-res[i-1])
        ans.append(res[0]+1)
        ans.reverse()

        print(ans)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20