Leetcode 763. Partition Labels (python+cpp)

Leetcode 763. Partition Labels

• 題目
• 解法1：轉化成interval overlapping問題
• 解法2：隻記錄字元結束位置

題目

解法1：轉化成interval overlapping問題

仔細觀察這個問題可以發現，其實可以轉化成interval的問題，采用類似435的思想來做，具體流程為：

• 首先以字母開始位置的index作為interval的開始，結束的位置作為interval結尾
• 接下來采取的方式跟435非常類似，周遊比較目前interval和下一個interval
• 如果目前interval的結束位置比下一個interval的開始位置大的話，證明這兩個interval有相交，也就證明目前還不能劃分出一個符合要求的subtring來
• 一直按照這樣的方式周遊下去，但是需要不斷更新相交的interval中最晚結束的位置。一旦找到一個interval開始位置與目前的結束位置不相交時，就證明前面可以劃分出一個符合要求的substring了

python代碼如下：

class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        start = {}
        for i, c in enumerate(S):
            if c not in start:
                start[c] = i
        end = {c: i for i, c in enumerate(S)}
        intervals = []
        for k,v in start.items():
            intervals.append((v,end[k]))
        ans = []
        prev = intervals[0][1]
        first = intervals[0][0]
        for i in range(1,len(intervals)):
            if prev>intervals[i][0]:
                prev = max(prev,intervals[i][1])
                first = min(first,intervals[i][0])
            else:
                ans.append(prev-first+1)
                prev = intervals[i][1]
                first = intervals[i][0]
        ans.append(prev-first+1)
        return ans
           

C++版本

class Solution {
public:
    vector<int> partitionLabels(string S) {
        if(S.size() == 0) return {};
        vector<int> ends(26,-1);
        for(int i=0;i<S.size();i++){
            ends[S[i] - 'a'] = i;
        }
        int prev_start = 0, prev_end = ends[S[0]-'a'];
        vector<int> ans;
        for(int i=1;i<S.size();i++){
            if(i <= prev_end){
                prev_end = max(prev_end,ends[S[i]-'a']);
            }else{
                ans.push_back(prev_end-prev_start+1);
                prev_end = ends[S[i]-'a'];
                prev_start = i;
            }
        }
        ans.push_back(prev_end-prev_start+1);
        return ans;
        
    }
};
           

解法2：隻記錄字元結束位置

直接上leetcode的官方解說吧：

We need an array last[char] -> index of S where char occurs last. Then, let anchor and j be the start and end of the current partition. If we are at a label that occurs last at some index after j, we’ll extend the partition j = last[c]. If we are at the end of the partition (i == j) then we’ll append a partition size to our answer, and set the start of our new partition to i+1.

python代碼：

class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        
        last = {c: i for i, c in enumerate(S)}
        j = anchor = 0
        ans = []
        for i, c in enumerate(S):
            j = max(j, last[c])
            if i == j:
                ans.append(i - anchor + 1)
                anchor = i + 1
            
        return ans
           

C++版本代碼：

class Solution {
public:
    vector<int> partitionLabels(string S) {
        vector<int> last(26);
        for (int i=0; i<S.length();i++) last[S[i]-'a'] = i;
        vector<int> ans;
        int j = 0, anchor = 0;
        for (int i=0;i<S.length();++i){
            if (last[S[i]-'a']>j) j = last[S[i]-'a'];
            if (i==j) {
                ans.push_back(i-anchor+1);
                anchor=i+1;
            }
        }
        return ans;
        
    }
};