763. Partition Labels

Loading...LeetCode

不知道是该叫它sliding window还是三指针...

先设置双指针l,r，从头开始遍历：

1. 将右指针r直接移动到目前遇到的字符所出现的最后一个位置（最右位置）

2. 然后对左右指针之间的字符进行遍历（i指针），根据遇到的字符去扩展目前i遍历的右边界（即r，只扩大，不回缩），直到i和r相交（即l与r之间的所有字符都不会再在右侧出现），记录一下当前长度为一个结果。

3. 将l指针移到r的右边，开始下一个对i的遍历。

class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        count = collections.Counter(S)
        rightMost = {ch: S.rindex(ch) for ch in count.keys()}
        
        res = []
        l, r = 0, 0
        ## step 1
        while l < len(S) and r < len(S):
            r = rightMost[S[l]]
            ## step 2
            i = l
            while i != r:
                r = max(r, rightMost[S[i]])
                i += 1
            res.append(r-l+1)
            ## step 3
            l = r+1

        return res