[LC-763][chapter2][Greedy Algorithm] Partition Labels 划分字母区间

[renchord]

tag: 贪心算法 英文链接： https://leetcode.com/problems/partition-labels/

中文描述： 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例：

输入：S = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释： 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。 提示： S的长度在[1, 500]之间。 S只包含小写字母 'a' 到 'z' 。

解题思路 ： 读第一遍题目的时候有些费解，什么叫同一个字母最多 出现在一个片段中，还花了N分钟去读题。不得不说有些时候翻译就是很蹩脚呀~~ 该题的目的是，针对一个字符串s，找到一个分隔方式(不打乱原来的顺序)，使得分开的每一个子字符串中的任意一个字符，不会出现在别的子串中，找到使子字符串 数目最多的分隔方式！ 又是一个经典的贪心算法！ 用朴素的思想来分析一下🌰例子

S = "ababcbacadefegdehijhklij"

我们取第一个字符 \'a\'，很显然，在最终结果里面如果存在子字符串T，必须包括所有的a，而该字符串S中a “右边界”位于 索引8 的地方，即最终结果中的某个字符串T包含了a字符，则它的区间至少包括了[0, 8]； 进一步的，由于需要满足 “同一字母最多出现在一个片段中”的特性，我们还需要去找[0,8]区间里的其它字符的最小囊括区间，不断的去拓展“右边界”。

聪明的你已经发现了，每个字符我们其实关心的是它的右边界，我们想到用一个map来统计某个字符在字符串中“最后”出现的位置； 题目提示我们最多26个小写字母，因此我们用一个int的数组就可以了。

我们用left标记当前遍历到的字符位置，right标记当前的右边界； 在第二层while循环中，退出的条件是left == right， 我们还需要一个before_left记录每次进入第二层循环时left的值； 第二层while循环退出时，用right-before_left + 1可以得到区间的长度，并更新left = right +1; 代码见下：

class Solution {
public:
    vector<int> partitionLabels(string s) {

        vector<int> lastpos(26, 0);
        for(int i = 0; i < s.size(); ++i)
        {
            lastpos[s[i] - 'a'] = i; //mark the last pos of char in s[i]
        }

        int left = 0;
        vector<int> res;
        while(left != s.size())
        {
            int right = lastpos[s[left] - 'a'];
            auto before_left = left;
            while(left != right && right != s.size() - 1)
            {
                if(lastpos[s[left] - 'a'] > right)
                    right = lastpos[s[left] - 'a'];
                left++;
            }
            res.push_back(right - before_left + 1);
            left = right + 1;
        }
        return res;

    }
};

有更好的思路可以继续讨论，预祝大家新年快乐~~

[renchord]

增加算法复杂度的分析： 空间分析： 我们需要一个额外的lastpos数组 长度为固定的26，res不作考虑，因此空间复杂度O(1); 时间分析：第一次循环对字符串进行统计处理，时间复杂度O(N)； 第二次是个两层循环，但实际上在该两次循环中只会遍历一次数组，每遍历到一个left位置时，会做一次查找，判断，left更新，潜在的right更新；以上操作都是常数级的； 最后是对res数组进行push_back的分析，这个不太好做，因为我们无法得到字符串的模式，这里做出一个假设，如果对于N长度的字符串，它的每个字符都是不一样的，那么我们需要做N次push_back， vector的push_back遵循动态扩容准则，当vector.size () - 1 == vector.capacity()时，会开辟一个新的vector_new，使得vector_new.size() == 2 * vector.size()， 并将原vector的内容拷贝到vector_new中。 我们用简单的数学分析一下可知，如果我们最终需要获得一个 规模为N的数组，则平均需要做lg2(N)次扩容操作，每次操作的次数由 1 -> 2 -> 4 -> N/2 ， 进行等比数列求和（可以用列项法展开算一下），我这边估算得到的结果还是O(N)级别的，因此整体的时间复杂度还是O(N)的。