763. 划分字母区间

原题地址

方法1-贪心

思路

就是按照题意来从左到右分析字符串 S ，得出不相交的区间。
具体步骤如下：

• 从第一个字母开始，假设是 'a' ，第一个区间一定包含最开始的 'a' 和结束的 'a' ；
• 然后分析第二个字母，假设是 'b' ，
• 如果开始的 'b' 在第一个区间之内，并且结束的 'b' 在第一个区间之外了，那么第一个区间就被扩充了，区间右端点应该改为 'b' 的结束位置；
• 举例来说，字符串 S='abbbabed' ， 'a' 的开始和结束位置分别为 0, 4 ，但是第一个区间的左右端点分别为 0, 5 。

所以我们的算法就是：遍历字符串，对于遇到的每一个字母，寻找他的结束位置，看是否能够更新当前区间的右侧端点。

我的想法如下：

1. 定义一个有序字典，遍历一遍字符串，来得到每个字符所出现的所有位置（用列表记录）；形如 {'a': [0, 3, 6], ...} ；
2. 然后遍历有序字典，用一个二维列表，记录每个字符出现的开始位置和结束位置；形如 [[0, 5], [1, 3], ...] ；
3. 然后再遍历二维列表，对于列表中的每一个字符的开始和结束位置：
   • 如果字符的开始位置和结束位置都位于当前区间内，则不更新当前区间，继续遍历下一个字符；
   • 如果字符的开始位置在当前区间内，结束位置在外，则更新当前区间的右侧端点；
   • 如果字符的开始位置在当前区间之外，则再开始新的区间；

于是就有了如下代码（太麻烦啦写的！！）

代码1

class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        from collections import OrderedDict
        oDict = OrderedDict()
        for i in range(len(S)):  # 得到有序字典
            if S[i] not in oDict:
                oDict[S[i]] = [i]
            else:
                oDict[S[i]].append(i)
        sList = []
        for lst in oDict.values():
            sList.append([lst[0], lst[-1]])  # 得到二维列表，里面存的是每个字符的开始和结束位置
        ans = []
        i = 0
        start = end = 0
        while i < len(sList):  # 遍历二维列表
            # 初始化当前区间
            start = sList[i][0]
            end = sList[i][-1]
            for j in range(i+1, len(sList)):
                print(i ,j)
                if sList[j][0] > end: #当前区间无法再更新，开始新的区间（对应第三种情况）
                    ans.append(end-start+1)
                    i = j-1
                    break
                else:
                    if sList[j][-1] > end:  # 更新当前区间的右端点（第二种情况）
                        end = sList[j][-1]
                if j == len(sList)-1:  #遍历完了，结束掉循环
                    i = j
            i += 1
        ans.append(end-start+1)
        return ans

时空复杂度

因为定义了有序字典和列表，空间复杂度毫无疑问是 O(N) ，
虽然下面有两重循环，但仔细观察就知道只遍历了二维数组一次，而且二维数组中的元素个数肯定等于 N ，所以时间复杂度也为 O(N)

代码2

官方给出的思路与我的一模一样，但是做法更好，写的代码也棒多了，附上官方代码

class Solution(object):
    def partitionLabels(self, S):
        # 通过enumerate得到每个字符的结束位置，(没有记录开始位置)
        last = {c: i for i, c in enumerate(S)}
        j = anchor = 0   #anchor 和 j 来表示当前区间的首尾。
        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
作者：LeetCode
链接：https://leetcode-cn.com/problems/partition-labels/solution/hua-fen-zi-mu-qu-jian-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时空复杂度

同代码1

代码3

cpp版

class Solution {
public:
    vector<int> partitionLabels(string S) {
        // 得到每个字符的右界
        int last[26];
        for(int i=0; i<26; i++) last[i] = -1;
        for(int i=0; i<S.size(); i++)     last[S[i]-'a'] = i;
        vector<int> v;
        int begin = 0, end = 0;
        for(int i=0; i<S.size(); i++){
            if(last[S[i]-'a'] > end){
                end = last[S[i]-'a'];
            }
            else if(i == end){
                v.push_back(end-begin+1);
                begin = end = i+1;
            }
        }
        return v;
    }
};