題目出處
難度
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]
而合併後，有分為兩種情況：
- - interval[1] >= end：類似交錯的情況，合併區間變為 [start, interval[1]]
- end >= interval[1]：類似包起來的情況，合併區間變為 [start, end]
以上的 1，2 又可以合併變為 [start, max(interval[1], end)]
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
input handling
x
Boundary conditions
見上述說明