動機

看到greedy解後恍然大悟

Problem

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Return a list of integers representing the size of these parts.

 

Example 1:

Input: s = ababcbacadefegdehijhklijOutput: [9,7,8]Explanation:The partition is ababcbaca, defegde, hijhklij.This is a partition so that each letter appears in at most one part.A partition like ababcbacadefegde, hijhklij is incorrect, because it splits s into less parts.

Example 2:

Input: s = eccbbbbdecOutput: [10]

 

Constraints:

  • 1 <= s.length <= 500
  • s consists of lowercase English letters.

Sol: stack

把每個字元當成一個一個區塊，如果stack中有出現過的字元就做interval merge

class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        stk = []
        for i in range(len(S)):
            j = len(stk)-1
            while j >= 0 and S[i] not in stk[j][1]:
                j -= 1
                
            if j < 0:
                stk.append([1,set([S[i]])])
            else:
                for _ in range(len(stk)-j-1):
                    tmp = stk.pop()
                    stk[-1][0] += tmp[0]
                    stk[-1][1] = stk[-1][1] | tmp[1]
                stk[-1][0] += 1
            #print(stk,S[:i+1])
        return [seg[0] for seg in stk]

Sol2: greedy

如果能知道每個字元的最後位置(hash)，就能知道這個區塊的最後位置!!

class Solution(object):
    def partitionLabels(self, S):
        last = {c: i for i, c in enumerate(S)}
        end = start = 0
        ans = []
        for i, c in enumerate(S):
            end = max(end, last[c])
            if i == end:
                ans.append(i - start + 1)
                start = i + 1
            
        return ans