Last Updated on 2022-03-24 by Clay
題目
You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.
Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.
Return a list of integers representing the size of these parts.
Example 1:
Input: s = "ababcbacadefegdehijhklij" Output: [9,7,8] Explanation: The partition is "ababcbaca", "defegde", "hijhklij". This is a partition so that each letter appears in at most one part. A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts.
Example 2:
Input: s = "eccbbbbdec" Output: [10]
Constraints:
1 <= s.length <= 500sconsists of lowercase English letters.
題目輸入一字串，我們要做的就是分割字串使字串中的每個字母在該分割段落中出現達到最多次。
題目只會有英文小寫字母，且有可能存在最長的分割段落就是原始字串本身（可能出現無法分割的情況）。
我們要回傳的，就是各個切割段落的長度。
以 Example 1 來說，就是原始字串 ababcbacadefegdehijhklij 可以被分割為 ababcbaca、defegde、hijhklij。直觀上來說，就是我們分割的段落中出現的字母是不可以出現在其他段落的，這樣才能保證在切割段落中該字母出現次數達到上限。
解題思路
Greedy 解法
首先先遍歷原始字串，並把每個不同的字母最後一次出現的位置記錄起來。
接著重新開始遍歷原始字串，並使用一個 end 變數來儲存當前出現過的所有字母中最後一個出現的位置。（這樣當我們遍歷到 end 時，可以保證我們把出現的每個字母都遍歷到最後一次了）
比方說 a 這個字母出現了，我們透過之前紀錄的字母最後出現位置知道了最後出現的地方是 8，那麼直到我們掃到第 8 個字母再次碰到 a 之前，我們都不能分割任何段落。
然而，若在中途，假設我們又碰到了一個字母 c 且其最後出現的位置在第 32，那麼我們在掃到 32 的位置之前就不可以停下來...... 依此類推。
那麼我們什麼時候可以分割呢？那當然就是當我們掃到的位置，剛好等於我們目前紀錄的最後一個字母位置，那代表目前出現過的所有字母我們都已經走訪過了，可以將這個段落的長度紀錄起來，並將下一個位置重新設為起點，繼續開始搜尋下一個段落...... 直到原始字串遍歷完畢。
Greedy 複雜度
因為我們需要遍歷兩次原始字串，故時間複雜度為 O(n)；
而我們最多只需要固定儲存 26 個字母的數量，以及每個段落的長度，所以空間複雜度可以視為 O(1)。
| Time complexity | O(n) |
| Space complexity | O(1) |
Greedy 解法 C++ 範例程式碼
class Solution {
public:
vector<int> partitionLabels(string s) {
// Init
int start = 0;
int end = 0;
vector<int> end_idx(26, 0);
vector<int> results;
// Record the last position of character
for (int i=0; i<s.size(); ++i) {
end_idx[s[i]-'a'] = i;
}
// Scanning string character
for (int i=0; i<s.size(); ++i) {
end = max(end, end_idx[s[i]-'a']);
if (i == end) {
results.push_back(i-start+1);
start = i + 1;
}
}
return results;
}
};Greedy 解法 Python 範例程式碼
class Solution:
def partitionLabels(self, s: str) -> List[int]:
# Init
start = 0
end = 0
end_idx = [0 for _ in range(26)]
results = []
# Record the last position of character
for i in range(len(s)):
end_idx[ord(s[i])-ord('a')] = i
# Scanning string character
for i in range(len(s)):
end = max(end, end_idx[ord(s[i])-ord('a')])
if i == end:
results.append(i-start+1)
start = i + 1
return results