【数据结构基础_字符串】Leetcode 763.划分字母区间

原题链接：Leetcode 763. Partition Labels

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

Example 1:

Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts.
1
2
3
4
5
6

Example 2:

Input: s = "eccbbbbdec"
Output: [10]
1
2

Constraints:

• 1 <= s.length <= 500
• s consists of lowercase English letters.

---

方法一：贪心

思路：

首先遍历一遍字符串，记录下每个字母的最后出现下标
再遍历字符串，用于找到进行划分的下标end。
end每次用max(end，list[s[i]])进行维护，当出现i = end时，说明在他之前的元素在i之后就都不会再出现了，此时就可以进行划分了

C++代码：

class Solution {
public:
    vector<int> partitionLabels(string s) {
        // 记录字母最后一次出现的下标
        int last[26];

        int length = s.size();
        
        // 更新最后出现的下标
        for (int i = 0; i < length; i++) {
            last[s[i] - 'a'] = i;
        }

        vector<int> ans;
        int start = 0, end = 0;
        for (int i = 0; i < length; i++) {
            
            // end是当前区间的结束下标
            end = max(end, last[s[i] - 'a']);

            // 说明之前遍历到的字母都再此时结束, 后面不会再出现了
            if (i == end) {
                ans.push_back(end - start + 1);
                start = end + 1;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

复杂度分析：

• 时间复杂度：O(n)，需要遍历字符串两遍
• 空间复杂度：O(1)，因为只包含小写字母，last[]里最多有26个元素