leetcode

commit 0c50ff9dddd1b1e1715044ade0c32d80961059c6
parent e352d7834c8b024e9f3c55ca4d10483220b8473b
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 30 Jul 2023 22:35:11 +0200

Daily Problem

Diffstat:
A
Problems/0664.cpp
 | 
22
++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 23 insertions(+), 0 deletions(-)
diff --git a/Problems/0664.cpp b/Problems/0664.cpp
@@ -0,0 +1,22 @@
+class Solution {
+  int dp[101][101];
+  int rec(const string &s, int l, int r) {
+    if (dp[l][r] != -1) return dp[l][r];
+    int res = s.size(), j = -1;
+    for (int i = l; i < r; i++) {
+      if (s[i] != s[r] && j == -1) j = i;
+      if (j != -1) res = min(res, 1 + rec(s, j, i) + rec(s, i + 1, r));
+    }
+    return dp[l][r] = j != -1 ? res : 0;
+  }
+
+public:
+  Solution() { memset(dp, 0xFF, sizeof(dp)); }
+  int strangePrinter(string &s) {
+    int j = 1;
+    for (int i = 1; i < s.size(); i++)
+      if (s[i] != s[i - 1]) s[j++] = s[i];
+
+    return rec(s, 0, j - 1) + 1;
+  }
+};
diff --git a/README.md b/README.md
@@ -327,6 +327,7 @@ for solving problems.
 |  0653  |    Easy    | [Two Sum IV - Input is a BST](Problems/0653.cpp)                                                 |
 |  0654  |   Medium   | [Maximum Binary Tree](Problems/0654.cpp)                                                         |
 |  0662  |   Medium   | [Maximum Width of Binary Tree](Problems/0662.cpp)                                                |
+|  0664  |    Hard    | [Strange Printer](Problems/0664.cpp)                                                             |
 |  0669  |   Medium   | [Trim a Binary Search Tree](Problems/0669.cpp)                                                   |
 |  0671  |    Easy    | [Second Minimum Node In a Binary Tree](Problems/0671.cpp)                                        |
 |  0673  |   Medium   | [Number of Longest Increasing Subsequence](Problems/0673.cpp)                                    |