[Day 16] Leetcode 763. Partition Labels (C++)

前言

今天要解的题目是top 100 liked里面的763. Partition Labels这题~ 这题的tag包含hash table, two pointers, string及greedy，一起来看看怎麽解吧！

想法

首先这个题目可以重新整理一下，变成更单纯的题目条件。题目要求是string的切分方法要让每个character只出现在其中一个substring，所以其实就=每个字母第一次出现跟最後一次出现要被划分在同一个substring中。
而因为之前写过56. Merge Intervals这题，所以我非常直觉地把这题转换成那题的逻辑来看，拆分成两大部分：

1. 列出每个字母第一次出现/最後一次出现的位置
2. 变成merge intervals题目─若interval与interval之间有交错，就进行融合

而merge intervals的解法则很简单：按照每个intervals的start进行排列，之後遍历比较後面每个intervals的start是否有早於前面intervals的end，若没有就可以直接新增新的intervals在後面(不须融合)，而若有则更新目前interval的end。

采用这个逻辑，整个程序码如下：

class Solution {
public:
    vector<int> partitionLabels(string s) {
        // turn each character first appears and last appears into intervals
        // save the appearing order of characters
        unordered_map<char, int> seen;
        vector<pair<int, int>> intervals;
        int idx=0;
        for(int i=0;i<s.length();++i){
            // not seen, initial the interval
            if(!seen.count(s[i])){
                intervals.push_back({i,i});
                seen[s[i]]=idx;
                ++idx;
            }
            // seen, update the last position
            else{
                intervals[seen[s[i]]].second=i;
            }
        }
        // if interval not overlapped, add the partition
        vector<int> ans;
        int last=intervals[0].second;
        int start=intervals[0].first;
        for(int i=1; i<intervals.size();++i){
            if(intervals[i].first>last){
                ans.push_back(last-start+1);
                start = intervals[i].first;
                last = intervals[i].second;
            }else{
                last=max(last, intervals[i].second);
            }
            
        }
        ans.push_back(last-start+1);
        return ans;
        
    }
};

而我也看到不少其他人写法是比较单纯的方式，没有转换那麽多层，也可以参考看看，摘录其中一个解答如下(新增了一些注解部分)：

class Solution {
public:
    vector<int> partitionLabels(string S) {
        // save the last position of each character
        vector<int> last(26,0);
        for(int i=0;i<S.size();i++) 
            last[S[i]-'a']=i;
        
        vector<int> res;
        int j=0,k=0;
        // iterate over the string again
        for(int i=0;i<S.size();i++) {
            // update the end of current interval(max of current end and the current charater last appear position)
            j = max(j, last[S[i]-'a']);
            // if this interval can end at this position, add the partition
            if(i==j) {
                res.push_back(i-k+1);
                k=i+1;
            }
        }
        return res;
    }
};

以上时间复杂度都为O(n)，对整个string进行遍历2次。

结语

连假已结束~ 好好把这下半个月拚完吧！