Formatted question description: https://leetcode.ca/all/664.html
664. Strange Printer (Hard)
There is a strange printer with the following two special requirements:
- 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 ending at any places, and will cover the original existing characters.
Given a string consists of lower English letters only, your job is to count the minimum number of turns the printer needed in order to print it.
Example 1:
Input: "aaabbb" Output: 2 Explanation: Print "aaa" first and then print "bbb".
Example 2:
Input: "aba" Output: 2 Explanation: Print "aaa" first and then print "b" from the second place of the string, which will cover the existing character 'a'.
Hint: Length of the given string will not exceed 100.
Related Topics:
Dynamic Programming, Depth-first Search
Similar Questions:
Solution 1. DP
// OJ: https://leetcode.com/problems/strange-printer/
// Time: O(N^3)
// Space: O(N^2)
// Ref: https://leetcode.com/problems/strange-printer/discuss/106810/Java-O(n3)-DP-Solution-with-Explanation-and-Simple-Optimization
class Solution {
public:
int strangePrinter(string s) {
if (s.empty()) return 0;
int N = s.size();
vector<vector<int>> dp(N, vector<int>(N));
for (int i = 0; i < N; ++i) {
dp[i][i] = 1;
if (i > 0) dp[i - 1][i] = s[i - 1] == s[i] ? 1 : 2;
}
for (int len = 3; len <= N; ++len) {
for (int i = 0; i + len <= N; ++i) {
int val = len;
for (int j = 0; j < len - 1; ++j) {
val = min(val, dp[i][i + j] + dp[i + j + 1][i + len - 1] - (s[i + j] == s[i + len - 1]));
}
dp[i][i + len - 1] = val;
}
}
return dp[0][N - 1];
}
};
Solution 2. DP
// OJ: https://leetcode.com/problems/strange-printer/
// Time: O(N^3)
// Space: O(N^2)
// Ref: https://leetcode.com/problems/strange-printer/discuss/106810/Java-O(n3)-DP-Solution-with-Explanation-and-Simple-Optimization/342701
class Solution {
public:
int strangePrinter(string s) {
if (s.empty()) return 0;
int N = s.size();
vector<vector<int>> dp(N, vector<int>(N));
for (int j = 0; j < N; ++j) {
for (int i = j; i >= 0; --i) {
dp[i][j] = i == j ? 1 : (1 + dp[i + 1][j]);
for (int k = i + 1; k <= j; ++k) {
if (s[k] != s[i]) continue;
dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k][j]);
}
}
}
return dp[0][N - 1];
}
};
Java
class Solution {
public int strangePrinter(String s) {
if (s == null || s.length() == 0)
return 0;
int length = s.length();
if (length == 1)
return 1;
int[][] dp = new int[length][length];
for (int i = 0; i < length; i++)
dp[i][i] = 1;
for (int i = length - 2; i >= 0; i--) {
for (int j = i + 1; j < length; j++) {
dp[i][j] = dp[i + 1][j] + 1;
for (int k = i + 1; k <= j; k++) {
if (s.charAt(k) == s.charAt(i))
dp[i][j] = Math.min(dp[i][j], dp[i + 1][k - 1] + dp[k][j]);
}
}
}
return dp[0][length - 1];
}
}