763. 划分字母区间

763. 划分字母区间

问题

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

示例 1：

输入：S = “ababcbacadefegdehijhklij”
输出：[9,7,8]
解释：
划分结果为 “ababcbaca”, “defegde”, “hijhklij”。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。

提示：

S的长度在[1, 500]之间。
S只包含小写字母 ‘a’ 到 ‘z’ 。

分析

dp：

一个很自然的想法是用map的key存26个字母，value为对应的片段的标号。对当前字符c，分在map和不在map两种情况，然后分别考虑如何更新res和map。

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
30
31
32
class Solution {
    /*
    对第i个元素，如果之前出现过，且在第j个片段中，接下来有两个操作：
    1. 将j之后的片段的个数都加在j后并删除，j的字符个数再加1；
    2. 将j之后片段里的字符的哈希表的value都改为j；
        具体操作方式为：遍历哈希表，对value大于j的值的key，将其value重设为j；
    对第i个元素，如果之前没出现过，接下来也有两个操作：
    1. 在res中新增一个片段；
    2. 更新hash表；
    */
    public List<Integer> partitionLabels(String S) {
        List<Integer> res = new ArrayList<>();
        Map<Character, Integer> hash = new HashMap<>();
        for (int i = 0; i < S.length(); ++i) {
            char c = S.charAt(i);
            if (hash.containsKey(c)) {
                int partIndex = hash.get(c);
                while (res.size() - 1 > partIndex) {
                    res.set(partIndex, res.get(partIndex) + res.remove(res.size() - 1));
                }
                res.set(partIndex, res.get(partIndex) + 1);
                for (Character key: hash.keySet()) {
                    if (hash.get(key) > partIndex) {hash.put(key, partIndex);}
                }
            } else {
                res.add(1);
                hash.put(c, res.size() - 1);
            }
        }
        return res; 
    }
}

greedy：

发现：同一个字母的第一次出现的下标位置和最后一次出现的下标位置必须出现在同一个片段。如果遍历字符串，得到每个字母最后一次出现的下标位置，则必然满足一个贪心策略：对于当前的字符c，对应的最后一次出现的下标位置一定不会大于片段的右边界。

如果用$start$和$end$分别表示一个片段的左右边界，那么对于当前字符c，它的右边界下标$end_c$一定小于等于它所在片段的右边界下标$end$。而$end$等于该片段内所有字符的右边界的最大值。因此可以遍历每个字符，不断的更新$end$，$end = max(end, end_c)$，而当遍历到$end$的时候就完成了一个片段的检索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<Integer> partitionLabels(String S) {
        List<Integer> res = new ArrayList<>();
        int[] hash = new int[26];
        int start = 0, end = 0;
        for (int i = 0; i < S.length(); ++i) {
            hash[S.charAt(i) - 'a'] = i;
        }
        for (int i = 0; i < S.length(); ++i) {
            end = Math.max(end, hash[S.charAt(i) - 'a']);
            if (i == end) {
                res.add(end - start + 1);
                start = i + 1;
            }
        }
        return res;
    }
}