划分字母区间

Leetcode Link: 763. 划分字母区间 - 力扣（LeetCode）

题目

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

解法一

思路：贪心，每次都划分出满足要求最小的，那么最终切分出来的就是最多的

难点：怎么保证当前的子字符串内的每一个字符在后面都没出现过 解决：用字典计数，来一个减一个，然后检查子字符串内的每个字符的在字典中的计数是不是为0

题解：

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
		## 创建统计字典
        lookup = collections.defaultdict(int)
        for c in s:
            lookup[c] += 1
        ## 解决问题
        res = []  # 结果
        cur_len = 0 # 当前子字符串的长度
        cont = set()  # 保存当前子字符串内的内容
        flag = 1   # 切分标志，1表示切
        for p in range(len(s)):
	        # 添加新来的到子字符串内容中
            if s[p] not in cont:
                cont.add(s[p])
			# 相关操作
            cur_len += 1
            lookup[s[p]] -= 1
			# 检查是不是在这一位后面可以切分了
            flag = 1
            for c in cont:
                if lookup[c] != 0: 
	                # 子字符串中有非0的，说明后面还会出现，不能切分
                    flag = 0
                    break
            
            if flag:  # 切分操作
                res.append(cur_len)
                cur_len = 0
                cont = set()
        return res

解法二

思路：代码随想录中的思路

如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。 此时前面出现过所有字母，最远也就到这个边界了。

可以分为如下两步：

1. 统计每一个字符最后出现的位置
2. 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

如图：

题解：

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
	    ### 每个字符最后出现的位置
        hash = [0] * 26
        for i in range(len(s)):
            hash[ord(s[i]) - ord('a')] = i
        
        result = []
        left = 0   # 起点位置
        right = 0  # 当前子字符串内所有字符最远出现位置
        for i in range(len(s)):
            right = max(right, hash[ord(s[i]) - ord('a')])
            if i == right:
                result.append(right - left + 1)
                left = i + 1
        return result

启发和联系