LeetCode763 Partition Labels

Posted on Edited on In

题目描述

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

1
Input: S = "ababcbacadefegdehijhklij"

1
Output: [9,7,8]
1
2
3
4
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

解析

根据题意，我们是要将一个字符串划分为若干个区间，任何单个的字符都只能出现在一个区间内，通过简单的模拟题意，很容易发现，这是一个可以利用贪心得以解决的问题。

先扫一遍字符串，求出每个字符开始位置和终止位置。在第二次扫描时，每次向后读取一个字符，更新最大终止位置，求出区间长度，当扫描的index到达当前最大终止位置，则说明这段区间所有的字符都出现且仅出现在该区间内，此时保存位置即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> partitionLabels(String S) {
    int[] last = new int[26];
    for (int i = 0; i < S.length(); ++i)
        last[S.charAt(i) - 'a'] = i;
    
    int j = 0, anchor = 0;
    List<Integer> res = new ArrayList();
    for (int i = 0; i < S.length(); ++i) {
        j = Math.max(j, last[S.charAt(i) - 'a']);
        if (i == j) {
            res.add(i - anchor + 1);
            anchor = i + 1;
        }
    }
    return res;
}

Tips

  1. 如果需要对英文或者数字字符进行hash，可以直接使用数组，不必从头再建立一个HashMap
  2. 本题曾出现在Amazon OA中