想要精通算法和SQL的成长之路 - 划分字母区间

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 划分字母区间

原题链接

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

示例：

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

看到这个题目，我先观察了一下示例的返回。试想一下，是根据什么来进行划分的？

如果下一个元素和当前元素不一致，就划分一个，那么结果就应该是： [“a”,“b”…]。那么肯定是不对的。

---

那么如果是下一个元素（i+1）以及下下个元素（i+2），都和当前元素不一致，就划分一个。貌似也不对：那么前几个应该是：[“aba”,“bcb”,“aca”…]。

• 遍历到a（下标为2）的时候，发现后面的b和c都不一致。
• 遍历到b（下标为3）的时候，发现后面的a和c都不一致。

---

到这里就能发现，从这个角度来思考肯定是走不通的，那么我们可以这么想：

• 遍历字符串的时候，记录每个字符串它目前出现过的最远位置。
• 当你遍历到某个字符串的时候，发现当前位置就是之前遍历过的所有字母的最远边界，那么当前位置就是分割点。

1.1 记录每个字母出现的最远位：

首先：

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

那么我们可以用一个固定大小的数组，统计a-z中的所有字母，它在字符串中最后出现的位置是哪里。

int[] lastIndex = new int[27];
for (int i = 0; i < s.length(); i++) {
    lastIndex[s.charAt(i) - 'a'] = i;
}
1
2
3
4

1.2 分割区间

遍历过程中，我们如何确定当前分割区间的右边界？

1. 维护当前分割区间的最远右边界值curMaxRight。
2. 一旦当前的遍历下标 i 和 curMaxRight 相等，就说明到达分割边界。
3. 因为我们要计算区间长度，因此光有一个右边界还不够，还需要一个左边界left。找到分割边界的时候，左边界就好处理了，下一个左边界就是curMaxRight+1。

// 记录左边界和右边界
int left = 0, curMaxRight = 0;
for (int i = 0; i < s.length(); i++) {
    // 当前这个字符对应的最原位置
    int lastIndex = lastIndexArr[s.charAt(i) - 'a'];
    // 遍历的同时，还要更新当前区间中重复出现的最远位置。
    curMaxRight = Math.max(curMaxRight, lastIndex);
    // 如果两者相等，说明当前位置就是边界值
    if (curMaxRight == i) {
        // 计入结果,计算当前区间的大小
        res.add(curMaxRight - left + 1);
        // 更新左边界
        left = i + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

那么最终结果如下：

public List<Integer> partitionLabels(String s) {
   ArrayList<Integer> res = new ArrayList<>();

    int[] lastIndexArr = new int[27];
    for (int i = 0; i < s.length(); i++) {
        lastIndexArr[s.charAt(i) - 'a'] = i;
    }
    // 记录左边界和右边界
    int left = 0, curMaxRight = 0;
    for (int i = 0; i < s.length(); i++) {
        // 当前这个字符对应的最原位置
        int lastIndex = lastIndexArr[s.charAt(i) - 'a'];
        // 遍历的同时，还要更新当前区间中重复出现的最远位置。
        curMaxRight = Math.max(curMaxRight, lastIndex);
        // 如果两者相等，说明当前位置就是边界值
        if (curMaxRight == i) {
            // 计入结果,计算当前区间的大小
            res.add(curMaxRight - left + 1);
            // 更新左边界
            left = i + 1;
        }
    }
    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24