aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--string_compression3.c36
-rw-r--r--string_compression3.py34
2 files changed, 70 insertions, 0 deletions
diff --git a/string_compression3.c b/string_compression3.c
new file mode 100644
index 0000000..8836ce3
--- /dev/null
+++ b/string_compression3.c
@@ -0,0 +1,36 @@
+// 3163. String Compression III
+#include "leetcode.h"
+
+/*
+ * given a string 'word', compress it using the following algorithm: begin with
+ * an empty string 'comp'. while 'word' is not empty, use the following
+ * operation: remove a maximum length prefix of 'word' made of a single
+ * character 'c' repeating at most 9 times. append the length of the prefix
+ * followed by 'c' to 'comp'. return the string 'comp'
+ */
+
+char *compressedString(char *word) {
+ int n = strlen(word), cnt = 1, idx = 0;
+ char *comp = (char *)calloc(2 * n + 1, sizeof(char));
+ for (int i = 0; i < n; i++) {
+ if (i == n || word[i] != word[i + 1] || cnt == 9) {
+ comp[idx] = cnt + '0';
+ idx++;
+ comp[idx] = word[i];
+ idx++;
+ cnt = 1;
+ } else
+ cnt++;
+ }
+ comp[idx] = '\0';
+ return comp;
+}
+
+int main() {
+ char *w1 = "abcde", *w2 = "aaaaaaaaaaaaaabb";
+ char *cs1 = compressedString(w1);
+ char *cs2 = compressedString(w2);
+ printf("%s\n", cs1); // expect: 1a1b1c1d1e
+ printf("%s\n", cs2); // expect: 9a5a2b
+ free(cs1), free(cs2);
+}
diff --git a/string_compression3.py b/string_compression3.py
new file mode 100644
index 0000000..9461c0e
--- /dev/null
+++ b/string_compression3.py
@@ -0,0 +1,34 @@
+# 3163. String Compression III
+
+"""
+given a string 'word', compress it using the following algorithm: begin with
+an empty string 'comp'. while 'word' is not empty, use the following
+operation: remove a maximum length prefix of 'word' made of a single
+character 'c' repeating at most 9 times. append the length of the prefix
+followed by 'c' to 'comp'. return the string 'comp'
+"""
+
+
+class Solution(object):
+ def compressedString(self, word):
+ """
+ :type word: str
+ :rtype: str
+ """
+ comp, c = "", word[0]
+ cnt, n = 1, len(word)
+ for i in range(1, n):
+ if word[i] == c and cnt < 9:
+ cnt += 1
+ else:
+ comp += str(cnt) + c
+ c = word[i]
+ cnt = 1
+ comp += str(cnt) + c
+ return comp
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.compressedString(word="abcde"))
+ print(obj.compressedString(word="aaaaaaaaaaaaaabb"))