diff options
author | Jack Sangdahl <[email protected]> | 2024-08-20 20:23:35 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-08-20 20:23:35 -0600 |
commit | cd9a161a24fdc9656086a0fa9b078dd86bef8805 (patch) | |
tree | 972e0e4b046d2027c02d818a1829d429a09eb8ad | |
parent | 53ef9811af1c9e013ba8e9f379ea67724ffc0281 (diff) | |
download | leetcode-cd9a161a24fdc9656086a0fa9b078dd86bef8805.tar.gz leetcode-cd9a161a24fdc9656086a0fa9b078dd86bef8805.zip |
664. strange printer
-rw-r--r-- | strange_printer.c | 43 | ||||
-rw-r--r-- | strange_printer.py | 35 |
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")) |