2020-10-22 劃分字母區間

763. 劃分字母區間

字元串 

S

 由小寫字母組成。我們要把這個字元串劃分為盡可能多的片段，同一個字母隻會出現在其中的一個片段。傳回一個表示每個字元串片段的長度的清單。

示例 1：

輸入：S = "ababcbacadefegdehijhklij"
輸出：[9,7,8]
解釋：
劃分結果為 "ababcbaca", "defegde", "hijhklij"。
每個字母最多出現在一個片段中。
像 "ababcbacadefegde", "hijhklij" 的劃分是錯誤的，因為劃分的片段數較少。

           

提示：

• S

  的長度在

  [1, 500]

  之間。

• S

  隻包含小寫字母 

  'a'

   到 

  'z'

   。

解題思路

方法一：貪心算法 + 雙指針

思路與算法

由于同一個字母隻能出現在同一個片段，顯然同一個字母的第一次出現的下标位置和最後一次出現的下标位置必須出現在同一個片段。是以需要周遊字元串，得到每個字母最後一次出現的下标位置。

在得到每個字母最後一次出現的下标位置之後，可以使用貪心算法和雙指針的方法将字元串劃分為盡可能多的片段，具體做法如下。

從左到右周遊字元串，周遊的同時維護目前片段的開始下标 start 和結束下标 end，初始時 start=end=0。

對于每個通路到的字母 c，得到目前字母的最後一次出現的下标位置 end_c，則目前片段的結束下标一定不會小于 end_c，是以令 end=max(end,end_c)

當通路到下标 end 時，目前片段通路結束，目前片段的下标範圍是 [start,end]，長度為 end−start+1，将目前片段的長度添加到傳回值，然後令 start=end+1，繼續尋找下一個片段。

重複上述過程，直到周遊完字元串。

上述做法使用貪心的思想尋找每個片段可能的最小結束下标，是以可以保證每個片段的長度一定是符合要求的最短長度，如果取更短的片段，則一定會出現同一個字母出現在多個片段中的情況。由于每次取的片段都是符合要求的最短的片段，是以得到的片段數也是最多的。

由于每個片段通路結束的标志是通路到下标 end，是以對于每個片段，可以保證目前片段中的每個字母都一定在目前片段中，不可能出現在其他片段，可以保證同一個字母隻會出現在同一個片段。

# 單指針版本
class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        res = []
        ptr = 0
        length = 0
        
        while ptr < len(S):
            flag = 0
            s = S[ptr]
            r = S.rfind(s)
            
            for i in range(ptr, r):
                t = S[i]
                if S.rfind(t) > r:
                    length += i - ptr 
                    ptr = i
                    flag = 1
                    break
            if flag == 0:
                length += r - ptr + 1
                res.append(length)
                length = 0
                ptr = r + 1
        return res
           

# 雙指針版本
class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        last = [0] * 26
        for i, ch in enumerate(S):
            last[ord(ch) - ord("a")] = i
        
        partition = list()
        start = end = 0
        for i, ch in enumerate(S):
            end = max(end, last[ord(ch) - ord("a")])
            if i == end:
                partition.append(end - start + 1)
                start = end + 1
        
        return partition