関小君刷题记

题目大意：

划分字母区间

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

示例 1:

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

注意:

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=763

解题思路分析：

这道题目讲的很清楚，将一个字符串分成几个部分，要保证每一部分的子字符串内的字符都不能在其他子字符串中出现。这道题的解题思路大致如下：

1. 先遍历一遍字符串，目的是将每种字符在字符串中最终出现的位置index记录下来。
2. 第二次遍历字符串，查看当前字符最终出现的位置index，此时，至少到这个index为止是不能分割的。继续循环下一个字符，看它的最终出现的index在哪，如果大小于前一个字符的最终index可以无视，如果大于的话说明到当前这个字符的最终index为止是不能被分割的，以此类推，直到当前index等于与之前记录的所有最终index的最大值相同时，说明此index之后再无之前的任何字符，此时可以分割。之后的循环同理。

看下代码：

public List<Integer> partitionLabels(String S) {
    List<Integer> res = new ArrayList<>(); // 定义返回结果
    int length = S.length(); // 字符串S的长度
    // 用于记录每个字符在S中最终出现的index
    int[] charRightIndex = new int[26];
    for (int i = 0; i < length; i++) {
        charRightIndex[S.charAt(i)- 'a'] = i;
    }
    int rightIndex = 0; // 用于记录当前字符最终出现的index
    int lastEndIndex = -1; // 用于记录上一次分割的位置
    for (int i = 0; i < length; i++) {
        // 如果当前字符的最终index大于之前的，更新rightIndex值
        rightIndex = Math.max(rightIndex, charRightIndex[S.charAt(i)- 'a']);
        // 当rightIndex等于当前index时，说明当前index之前的字符都已经出现过了
        if (rightIndex == i) {
            // 将长度加入到返回结果
            res.add(i - lastEndIndex);
            // 更新最终分割位置
            lastEndIndex = i;
        }
    }
    return res;
}

本题解法用时3ms。

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-763-partition-labels解题思路分析/