diff options
-rw-r--r-- | partition_labels.c | 42 | ||||
-rw-r--r-- | partition_labels.py | 34 |
2 files changed, 76 insertions, 0 deletions
diff --git a/partition_labels.c b/partition_labels.c new file mode 100644 index 0000000..eb06b60 --- /dev/null +++ b/partition_labels.c @@ -0,0 +1,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); +} diff --git a/partition_labels.py b/partition_labels.py new file mode 100644 index 0000000..13556c5 --- /dev/null +++ b/partition_labels.py @@ -0,0 +1,34 @@ +# 763. Partition Labels + +""" +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. +""" + + +class Solution(object): + def partitionLabels(self, s): + """ + :type s: str + :rtype: List[int] + """ + curr, ans = 0, [0] + ends = {c: i for i, c in enumerate(s)} + while curr < len(s): + prev = ends[s[curr]] + while curr <= prev: + sym = s[curr] + prev = max(prev, ends[sym]) + curr += 1 + ans.append(curr) + return [ans[i] - ans[i - 1] for i in range(1, len(ans))] + + +if __name__ == "__main__": + obj = Solution() + print(obj.partitionLabels(s="ababcbacadefegdehijhklij")) + print(obj.partitionLabels(s="eccbbbbdec")) |