題目出處

763. Partition Labels

難度

medium

個人範例程式碼

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        # partition need no word duplicate
        hashtable = self.set_hashtable(s)
        # print(hashtable)
        intervals = self.set_interval(hashtable)
        # print(intervals)
        intervals = self.merge_interval(intervals)
        # print(intervals)
        return [interval[1]-interval[0]+1 for interval in intervals] # 0~2 = 2-0+1

    def set_interval(self, hashtable):
        return [interval for interval in hashtable.values()]

    def merge_interval(self, intervals):
        ans = []

        for idx, interval in enumerate(intervals):
            if idx == 0:
                start = interval[0]
                end = interval[1]
            else:
                if end >= interval[0]:
                    end = max(interval[1], end)                    
                else: # no cross interval
                    ans.append([start, end])
                    start = interval[0]
                    end = interval[1]

        ans.append([start, end]) # last interval
        return ans

    def set_hashtable(self, s):
        hashtable = {}
        for idx, word in enumerate(s):
            if word not in hashtable:
                hashtable[word] = [idx, idx]
            else:
                hashtable[word][1] = idx
        return hashtable

算法說明

這題是 interval 系列的變化題，我們可以建立一個 hashtable，
紀錄每一個單字的 [起始, 結束] 位置。

最後因為題目要求最大化 interval 數量，但需要盡量保持不重複數字
(這邊直接就當作同一個字母，「不能出現在不同區間啦！」題目敘述太繞了!)

因此，我們先用文字組出每一個區間，然後合併區間。就是一個這樣的題目了!

討論 interval 合併的策略

主要情況有兩種：

先固定好 start 的順序，
假設後進來的 [interval[0], interval[1]]

有要合併的條件： end >= interval[0]

而合併後，有分為兩種情況：

1. interval[1] >= end：類似交錯的情況，合併區間變為 [start, interval[1]]
2. end >= interval[1]：類似包起來的情況，合併區間變為 [start, end]

以上的 1，2 又可以合併變為 [start, max(interval[1], end)]

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

input handling

x

Boundary conditions

見上述說明

Reference

• https://www.facebook.com/groups/1451299754892511/posts/5171314816224301/