aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-08-20 20:23:35 -0600
committerJack Sangdahl <[email protected]>2024-08-20 20:23:35 -0600
commitcd9a161a24fdc9656086a0fa9b078dd86bef8805 (patch)
tree972e0e4b046d2027c02d818a1829d429a09eb8ad
parent53ef9811af1c9e013ba8e9f379ea67724ffc0281 (diff)
downloadleetcode-cd9a161a24fdc9656086a0fa9b078dd86bef8805.tar.gz
leetcode-cd9a161a24fdc9656086a0fa9b078dd86bef8805.zip
664. strange printer
-rw-r--r--strange_printer.c43
-rw-r--r--strange_printer.py35
2 files changed, 58 insertions, 20 deletions
diff --git a/strange_printer.c b/strange_printer.c
index 6a84b90..abb9d26 100644
--- a/strange_printer.c
+++ b/strange_printer.c
@@ -1,8 +1,5 @@
// 664. Strange Printer
-#include <math.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
+#include "leetcode.h"
/*
* there is a strange printer with the following two special properties:
@@ -12,26 +9,32 @@
* 's', return the minimum number of turns the printer needed to print it.
*/
-int f[100][100];
-
-int dfs(char *s, int left, int right) {
- if (left > right)
- return 0;
- if (f[left][right])
- return f[left][right];
- f[left][right] = dfs(s, left, right - 1) + 1;
- for (int i = left; i < right; i++) {
- if (s[i] == s[right])
- f[left][right] =
- fmin(f[left][right], dfs(s, left, i) + dfs(s, i + 1, right - 1));
+int get_cnt(char *s, int **dp, int r, int l) {
+ if (dp[r][l] != -1)
+ return dp[r][l];
+ else {
+ int i = r;
+ while (i < l && s[i] == s[l])
+ i++;
+ int min = l - i;
+ for (int j = i; j < l; j++)
+ if (get_cnt(s, dp, i, j) + get_cnt(s, dp, j + 1, l) + 1 < min)
+ min = get_cnt(s, dp, i, j) + get_cnt(s, dp, j + 1, l) + 1;
+ dp[r][l] = min;
+ return dp[r][l];
}
- return f[left][right];
}
int strangePrinter(char *s) {
- memset(f, 0, sizeof(f));
- int len = strlen(s);
- return dfs(s, 0, len - 1);
+ int n = strlen(s);
+ int **dp = (int **)malloc(n * sizeof(int *));
+ for (int i = 0; i < n; i++) {
+ dp[i] = (int *)malloc(n * sizeof(int));
+ dp[i][i] = 0;
+ for (int j = i + 1; j < n; j++)
+ dp[i][j] = -1;
+ }
+ return get_cnt(s, dp, 0, n - 1) + 1;
}
int main() {
diff --git a/strange_printer.py b/strange_printer.py
new file mode 100644
index 0000000..abc8899
--- /dev/null
+++ b/strange_printer.py
@@ -0,0 +1,35 @@
+# 664. Strange Printer
+
+"""
+there is a strange printer with the following two special properties:
+- the printer can only print a sequence of the same character each time
+- at each turn, the printer can print new characters starting from and eding
+at any place and will cover the origin existing characters given a string
+'s', return the minimum number of turns the printer needed to print it.
+"""
+
+
+class Solution(object):
+ def strangePrinter(self, s):
+ """
+ :type s: str
+ :rtype: int
+ """
+ n = len(s)
+ dp = [[0] * n for _ in range(n)]
+ for i in range(n - 1, -1, -1):
+ dp[i][i] = 1
+ for j in range(i + 1, n):
+ if s[i] == s[j]:
+ dp[i][j] = dp[i][j - 1]
+ else:
+ dp[i][j] = dp[i][j - 1] + 1
+ for k in range(i, j):
+ dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])
+ return dp[0][n - 1]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.strangePrinter("aaabbb"))
+ print(obj.strangePrinter("aba"))