LeetCode - Partition Labels（分隔字母區間）

題目描述

給定一個字符串 s，請將字符串劃分成若干個片段，使得每個字母只出現在其中的一個片段中。返回一個列表，表示每個片段的長度。

範例：

輸入：s = "ababcbacadefegdehijhklij"
輸出：[9,7,8]
解釋：
- 第一個片段是 "ababcbaca"，長度為 9。所有出現在該片段的字符都不會出現在其他片段。
- 第二個片段是 "defegde"，長度為 7。
- 第三個片段是 "hijhklij"，長度為 8。

解法思路

我們的目標是確保每個字符只出現在一個片段中。因此，可以按照以下步驟來解決問題：

1. 記錄每個字符的最後出現位置：遍歷字符串，使用哈希表（字典）記錄每個字符的最後出現位置，這樣在劃分區間時可以確保所有該字符出現在同一個片段內。

2. 劃分區間：

   • 使用兩個指針 start 和 end，start 表示當前片段的起始位置，end 表示當前片段的結束位置。
   • 從字符串的起點開始遍歷，對每個字符更新 end 為該字符的最後出現位置（保證該字符不會出現在下一個片段中）。
   • 當遍歷到的索引等於 end 時，說明當前片段已完成劃分，將其長度加入結果列表，然後將 start 更新為下一個片段的起點。

範例代碼

以下是 Python 的實現：

def partitionLabels(s):
    # 1. 記錄每個字符的最後出現位置
    last_occurrence = {char: i for i, char in enumerate(s)}
    
    partitions = []
    start = end = 0
    
    # 2. 遍歷字符串
    for i, char in enumerate(s):
        end = max(end, last_occurrence[char])  # 更新當前片段的結束位置
        if i == end:  # 如果當前索引等於片段結束位置
            partitions.append(end - start + 1)  # 計算片段長度並加入結果
            start = i + 1  # 更新起始位置為下一個片段的起點
    
    return partitions

代碼解析

1. 記錄最後位置：使用字典 last_occurrence 存儲每個字符的最後出現索引。
2. 遍歷字符串並劃分片段：
   • 每遇到一個字符，更新當前片段的 end 為該字符的最後出現位置。
   • 當 i 等於 end 時，說明可以完成一個片段的劃分，計算該片段長度並將 start 更新至下一個片段的起始位置。
3. 返回結果：最終的 partitions 列表即為各個片段的長度。

時間和空間複雜度

• 時間複雜度：O(n)，其中 n 是字符串的長度。我們需要兩次遍歷字符串：一次記錄每個字符的最後出現位置，另一次劃分片段。
• 空間複雜度：O(1)，因為字母數量有限，last_occurrence 至多存儲 26 個字符。