Keshawn_lu's Blog

Leetcode 763. 划分字母区间

字数统计: 396阅读时长: 1 min
2020/10/22 Share

题目简介:

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

示例 1:

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

提示:

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

思路:

首先遍历一遍字符串,记录每个字符最后出现的位置

然后利用双指针,从头开始遍历,每次更新该片段字符出现的最远位置,若当前位置与之前片段字符的最远位置相同时(即right = i),说明找到了分割点,这个片段即为所求,长度为right - left + 1

代码如下:

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
26
27
28
29
class Solution {
public:
vector<int> partitionLabels(string S) {

int last[26];
vector<int> res;

for(int i = 0; i < S.size(); i++){

last[S[i] - 'a'] = i; //找到每个字符最后出现的位置
}

int left = 0;
int right = 0;

for(int i = 0; i < S.size(); i++){

right = max(right, last[S[i] - 'a']); //不断更新一个片段中字符出现的最远位置

if(i == right){ //当前位置为该片段字符的最远位置

res.push_back(right - left + 1); //找到了分割点
left = right + 1;
}
}

return res;
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: