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

 

示例 1：

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

 

提示：

• S的長度在[1, 500]之間。
• S只包含小寫字母 'a' 到 'z' 。

">

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

?

示例 1：

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

?

提示：

• S的長度在[1, 500]之間。
• S只包含小寫字母 'a' 到 'z' 。

貪心算法 + 雙指針

由于同一個字母只能出現在同一個片段，顯然同一個字母的第一次出現的下標位置和最后一次出現的下標位置必須出現在同一個片段。因此需要遍歷字符串，得到每個字母最后一次出現的下標位置。

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

• 從左到右遍歷字符串，遍歷的同時維護當前片段的開始下標 $\text{start}$ 和結束下標 $\text{end}$，初始時 $\text{start}=\text{end}=0$。

• 對于每個訪問到的字母 $c$，得到當前字母的最后一次出現的下標位置 endc\textit{end}_cendc?，則當前片段的結束下標一定不會小于 endc\textit{end}_cendc?，因此令 end=max?(end,endc)\textit{end}=\max(\textit{end},\textit{end}_c)end=max(end,endc?)。

• 當訪問到下標 $\text{end}$ 時，當前片段訪問結束，當前片段的下標范圍是 $[\text{start},\text{end}]$，長度為 $\text{end}?\text{start}+1$，將當前片段的長度添加到返回值，然后令 $\text{start}=\text{end}+1$，繼續尋找下一個片段。

• 重復上述過程，直到遍歷完字符串。

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

由于每個片段訪問結束的標志是訪問到下標 $\text{end}$，因此對于每個片段，可以保證當前片段中的每個字母都一定在當前片段中，不可能出現在其他片段，可以保證同一個字母只會出現在同一個片段。

Code

from typing import Listclass Solution:def partitionLabels(self, S: str) -> List[int]:last = [0 for _ in range(26)]for i, ch in enumerate(S):last[ord(ch) - ord('a')] = ipartition = list()start = end = 0for i, ch in enumerate(S):end = max(end, last[ord(ch) - ord('a')])if i == end:partition.append(end - start + 1)start = end + 1return partition

復雜度分析

• 時間復雜度：$O(n)$，其中 $n$ 是字符串的長度。需要遍歷字符串兩次，第一次遍歷時記錄每個字母最后一次出現的下標位置，第二次遍歷時進行字符串的劃分。

• 空間復雜度：$O(\Sigma )$，其中 $\Sigma$ 是字符串中的字符集大小。這道題中，字符串只包含小寫字母，因此 $\Sigma =26$。

總結

以上是生活随笔為你收集整理的763. Partition Labels 划分字母区间的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。