Welcome to Subscribe On Youtube
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];
}
};
-
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]; } } ############ class Solution { public int strangePrinter(String s) { int n = s.length(); int[][] f = new int[n + 1][n + 1]; for (int i = 0; i < n; ++i) { f[i][i] = 1; } for (int i = n - 2; i >= 0; --i) { for (int j = i + 1; j < n; ++j) { f[i][j] = 1 + f[i + 1][j]; for (int k = i + 1; k <= j; ++k) { if (s.charAt(i) == s.charAt(k)) { f[i][j] = Math.min(f[i][j], f[i + 1][k] + f[k + 1][j]); } } } } return f[0][n - 1]; } } -
// 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]; } }; -
class Solution: def strangePrinter(self, s: str) -> int: n = len(s) dp = [[inf] * 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: for k in range(i, j): dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]) return dp[0][-1] -
func strangePrinter(s string) int { n := len(s) dp := make([][]int, n) for i := range dp { dp[i] = make([]int, n) } for i := n - 1; i >= 0; i-- { dp[i][i] = 1 for j := i + 1; j < n; j++ { if s[i] == s[j] { dp[i][j] = dp[i][j-1] } else { dp[i][j] = 10000 for k := i; k < j; k++ { dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]) } } } } return dp[0][n-1] } func min(a, b int) int { if a < b { return a } return b } -
function strangePrinter(s: string): number { const n = s.length; const f: number[][] = new Array(n) .fill(0) .map(() => new Array(n).fill(1 << 30)); for (let i = n - 1; i >= 0; --i) { f[i][i] = 1; for (let j = i + 1; j < n; ++j) { if (s[i] === s[j]) { f[i][j] = f[i][j - 1]; } else { for (let k = i; k < j; ++k) { f[i][j] = Math.min(f[i][j], f[i][k] + f[k + 1][j]); } } } } return f[0][n - 1]; }