划分字母区间

发表于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

LeetCode每日一题，763. Partition Labels

先看题目描述

BiEGJe.png

大意就是给定一个字符串 S，让我们将 S 分为尽可能多的片段，要求每个字母最多只出现在其中一个片段

算法和思路

贪心算法

由于同一个字母只能出现在同一个片段，显然同一个字母的第一次出现的下标位置和最后一次出现的下标位置必须出现在同一个片段。因此需要遍历字符串，得到每个字母最后一次出现的下标位置

算法流程：

  • last 数组记录每个字母最后一次出现的下标位置，初始化 index 为 0，pre 为 -1
  • 移动 index 指针：
    • 将 index 移动到它对应字母最后一次出现的下标位置 last[S[index]]
    • 然后遍历 pre + 1 与 index 之间的所有字母 S[i]，若 last[S[i]] 大于 index，则更新 index 为 last[S[i]]
    • 结果列表 res 中添加 index - pre
    • 更新 pre 为 index
    • 将 index + 1
  • 重复上述过程直至 index 大于等于字符串 S 的长度

算法源码

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
import java.util.*;

class Solution {
    public List<Integer> partitionLabels(String S) {
        List<Integer> res = new ArrayList<Integer>();
        int len = S.length();
        int[] last = new int[26];
        for (int i = 0; i < len; i++) {
            last[S.charAt(i) - 'a'] = i;
        }
        int index = 0;
        int pre = -1;
        while (index < len) {
            index = last[S.charAt(index) - 'a'];
            for (int i = pre + 1; i < index; i++) {
                int cur = last[S.charAt(i) - 'a'];
                index = index > cur ? index : cur;
            }
            res.add(index - pre);
            pre = index;
            index++;
        }
        return res;
    }
}