Leetcode763-划分字母区间

解答

贪心策略为：从头开始搜索，使子串尽可能短。此题最关键的是事先确定每一个字符最后一次出现位置。

class Solution {
public:
    vector<int> partitionLabels(string S) {
        // 记录每个字母最后一次出现的位置
        map<char, int> lastPos;
        for (int i=0; i<S.size(); i++)
            lastPos[S[i]] = i;

        vector<int> retVec; 

        int pos = 0;
        while(pos < S.size()) {
            int startPos = pos;
            int endPos = lastPos[S[pos]];
            for (; pos <= endPos; pos++) {
                endPos = max(endPos, lastPos[S[pos]]);
            }
            retVec.push_back(pos - startPos);
        }
        return retVec;
    }
};