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
30
31
32
33
34
35
36
37
38
39
40
41
42
|
// 763. Partition Labels
#include "leetcode.h"
/*
* you are given a string 's'. we want to partition the string into as many
* parts as possible so that each letter appears in at most one part. for
* example, the string 'ababcc' can be partitioned into '["abab", "cc"]'. note
* that the partition is done so that after concatenating all the parts in
* order, the resultant string should be 's'. return a list of integers
* representing the size of these parts.
*/
int *partitionLabels(char *s, int *returnSize) {
int n = strlen(s), start = 0, end = 0, curr = 0;
int *ans = (int *)calloc(n, sizeof(int)), hash[26] = {0};
for (int i = 0; i < n; i++)
hash[s[i] - 'a'] = i;
for (int i = 0; i < n; i++) {
int prev = hash[s[i] - 'a'];
end = end > prev ? end : prev;
if (end == i) {
ans[curr++] = end - start + 1;
start = end + 1;
}
}
*returnSize = curr;
return ans;
}
int main() {
char *s1 = "ababcbacadefegdehijhklij", *s2 = "eccbbbbdec";
int rs1, *pl1 = partitionLabels(s1, &rs1);
int rs2, *pl2 = partitionLabels(s2, &rs2);
for (int i = 0; i < rs1; i++)
printf("%d ", pl1[i]); // expect: 9 7 8
printf("\n");
for (int i = 0; i < rs2; i++)
printf("%d ", pl2[i]); // expect: 10
printf("\n");
free(pl1);
free(pl2);
}
|