763. 划分字母区间

题目:https://leetcode-cn.com/problems/partition-labels/

代码:

class Solution {

    public List<Integer> partitionLabels(String S) {
        char[] chars = S.toCharArray();
        //统计a-z每个字母的开头和结尾位置
        int[][] letter = new int[26][2];
        for (int i = 0; i < 26; i++) {
            char c = (char) ('a' + i);
            letter[i][0] = S.indexOf(c);
            letter[i][1] = S.lastIndexOf(c);
        }
        //截取字符串获取结果
        List<Integer> res = new ArrayList<>();
        int start = 0;
        int end = 0;
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            if (letter[c - 'a'][0] > end) {
                //开启新的字符串,记录上一个字符串结果,设置新字符串start
                res.add(end - start + 1);
                start = letter[c - 'a'][0];
            }
            if (letter[c - 'a'][1] > end) {
                //设置end
                end = letter[c - 'a'][1];
            }
        }
        //记录最后一个结果
        res.add(end - start + 1);

        return res;
    }

}

定义一个二维数组,第一个维度为a-z,第二个维度记录2个值,字母c在字符串中的开头和结尾的索引值。

这样我们只需要通过一次遍历即可获得字符串S中每个字母的区间范围,接下来我们只需要对区间进行合并(有重合部分的区间合并成1个区间)

实现方法是:我们再次遍历S,这样我们对于一个区间的start就肯定是最小值,这个时候end值不确定,因为可能存在重合区间,所以end值可能会变大,需要通过继续遍历来确定end的最终值,具体实现参考代码。