Leetcode 763.划分字母区间

力扣传送门(opens new window)

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

示例：

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

提示：

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

解题思路：

看完题目一脸懵逼的我，根本读不懂好吧。

先说一下题目的大概意思：

让我们来看一个例子来更好地理解这个问题。给定字符串S = "ababcbacadefegdehijhklij"，我们可以将其划分为三个片段，分别是 "ababcbaca"、"defegde"和"hijhklij"。

仔细看这三个片段，

第一个片段出现的字母有a,b,c

第二个片段出现的字母有d,e,f,g

第三个片段出现的字母有h,i,j,k,l.

每个字母最多只出现在一个片段中!!!这就是这道题目的关键。

理解了题目之后，我们看这道题目的解题思路是什么。

还是使用贪心的策略来划分字符串。

1.我们首先遍历字符串S，记录每个字母最后一次出现的位置。

2.我们再次遍历字符串S，并使用两个指针start和end来表示当前片段的起始位置和结束位置。对于当前遍历到的字母，我们更新end为该字母最后一次出现的位置。

3.如果当前位置i等于end，那么我们已经遍历到了当前片段的结束位置，此时我们可以将该片段的长度加入结果列表，并将start更新为i+1，准备开始下一个片段的划分。

通过这种策略，我们可以保证每个字母最多只出现在一个片段中。遍历结束后，我们就能得到所有片段的长度列表作为最终的结果。

最后通过示例来具体说明一下：

给定字符串S = "ababcbacadefegdehijhklij"，我们首先记录每个字母最后一次出现的位置：

'a'的最后一次出现在索引8
'b'的最后一次出现在索引5
'c'的最后一次出现在索引7
'd'的最后一次出现在索引14
'e'的最后一次出现在索引15
'f'的最后一次出现在索引11
'g'的最后一次出现在索引13
'h'的最后一次出现在索引19
'i'的最后一次出现在索引22
'j'的最后一次出现在索引23
'k'的最后一次出现在索引20
'l'的最后一次出现在索引21

接下来，我们遍历字符串S并进行划分：
当遍历到索引0时，当前字母是'a'，并且'a'最后一次出现在索引8，所以我们更新end为8。
当遍历到索引1时，当前字母是'b'，并且'b'最后一次出现在索引5，这里更新end还是为8。
当遍历到索引2时，当前字母是'a'，并且'a'最后一次出现在索引8，这里更新end还是为8。
当遍历到索引3时，当前字母是'b'，并且'b'最后一次出现在索引5，这里更新end还是为8。
当遍历到索引4时，当前字母是'c'，并且'c'最后一次出现在索引7，这里更新end还是为8。

当遍历到索引5时，当前字母是'b'，并且'b'最后一次出现在索引5，这里更新end还是为8。

当遍历到索引6时，当前字母是'a'，并且'c'最后一次出现在索引8，这里更新end还是为8。

当遍历到索引7时，当前字母是'c'，并且'c'最后一次出现在索引7，这里更新end还是为8。

当遍历到索引8时，说明我们已经遍历到了当前片段的结束位置，此时我们可以将该片段的长度加入结果列表，并将start更新为i+1，准备开始下一个片段的划分。

通过这种方式，我们可以得到划分结果为 "ababcbaca"，然后继续进行下一个片段的划分，直到遍历结束。最终的结果列表为[9, 7, 8]，即每个字符串片段的长度。

希望这样解释能更加清楚地理解这道题目的解题思路。

代码实现：

import java.util.ArrayList;
import java.util.List;

public class StringPartition {

    public static List<Integer> partitionLabels(String S) {
        List<Integer> result = new ArrayList<>();

        // 记录每个字母最后一次出现的位置
        int[] lastOccurrences = new int[26];
        for (int i = 0; i < S.length(); i++) {
            lastOccurrences[S.charAt(i) - 'a'] = i;
        }

        int start = 0; // 当前片段的起始位置
        int end = 0; // 当前片段的结束位置

        // 遍历字符串S并进行划分
        for (int i = 0; i < S.length(); i++) {
            end = Math.max(end, lastOccurrences[S.charAt(i) - 'a']);
            if (i == end) { // 当前位置等于结束位置，说明遍历到了当前片段的结束位置
                result.add(end - start + 1); // 将当前片段的长度加入结果列表
                start = end + 1; // 更新下一个片段的起始位置
            }
        }

        return result;
    }

    public static void main(String[] args) {
        String S = "ababcbacadefegdehijhklij";
        List<Integer> partitionLengths = partitionLabels(S);
        System.out.println(partitionLengths);
    }
}

有收获的帮忙点个赞吧～

目录CONTENT

Leetcode 763.划分字母区间

Leetcode 763.划分字母区间

解题思路：

代码实现：

评论区