class Solution {
public:
int strangePrinter(string s) {
}
};
664. 奇怪的打印机
有台奇怪的打印机有以下两个特殊要求：
给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。
示例 1：
输入：s = "aaabbb" 输出：2 解释：首先打印 "aaa" 然后打印 "bbb"。
示例 2：
输入：s = "aba" 输出：2 解释：首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。
提示：
1 <= s.length <= 100s 由小写英文字母组成相似题目
原站题解
python3 解法, 执行用时: 492 ms, 内存消耗: 16 MB, 提交时间: 2023-06-02 09:47:26
class Solution:
def strangePrinter(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for Len in range(2, n + 1): #以区间的长度为clue
for L in range(0, n - Len + 1):
R = L + Len - 1 #L,R皆为实指
dp[L][R] = dp[L][R-1] + 1
for mid in range(L, R):
if s[mid] == s[R]:
dp[L][R] = min(dp[L][R], dp[L][mid] + dp[mid+1][R-1])
return dp[0][n-1]
python3 解法, 执行用时: 488 ms, 内存消耗: 16 MB, 提交时间: 2023-06-02 09:47:16
class Solution:
def strangePrinter(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for L in range(n-1, -1, -1): #L依赖于右侧
for R in range(L + 1, n): #R依赖于左侧
dp[L][R] = 1 + dp[L+1][R] #先单独打印L
for mid in range(L+1, R, 1): #选取中间点
if s[L] == s[mid]:
dp[L][R] = min(dp[L][R], dp[L][mid] + dp[mid+1][R])
if s[L] == s[R]: #端点相同(这2句一样)
dp[L][R] = min(dp[L][R], dp[L+1][R])
# dp[L][R] = dp[L][R-1]
return dp[0][n-1]
python3 解法, 执行用时: 932 ms, 内存消耗: 16.1 MB, 提交时间: 2023-06-02 09:47:06
class Solution:
def strangePrinter(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for L in range(n-1, -1, -1): #L依赖于右侧
for R in range(L + 1, n): #R依赖于左侧
if s[L] == s[R]:
dp[L][R] = dp[L][R-1]
else:
tmp = 1000
for mid in range(L, R, 1):
tmp = min(tmp, dp[L][mid] + dp[mid+1][R])
dp[L][R] = tmp
return dp[0][n-1]
golang 解法, 执行用时: 12 ms, 内存消耗: 6.1 MB, 提交时间: 2023-06-02 09:45:40
func strangePrinter(s string) int {
n := len(s)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, n)
}
for i := n - 1; i >= 0; i-- {
f[i][i] = 1
for j := i + 1; j < n; j++ {
if s[i] == s[j] {
f[i][j] = f[i][j-1]
} else {
f[i][j] = math.MaxInt64
for k := i; k < j; k++ {
f[i][j] = min(f[i][j], f[i][k]+f[k+1][j])
}
}
}
}
return f[0][n-1]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
javascript 解法, 执行用时: 112 ms, 内存消耗: 43.5 MB, 提交时间: 2023-06-02 09:45:28
/**
* @param {string} s
* @return {number}
*/
var strangePrinter = function(s) {
const n = s.length;
const f = new Array(n).fill(0).map(() => new Array(n).fill(0));
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 {
let minn = Number.MAX_SAFE_INTEGER;
for (let k = i; k < j; k++) {
minn = Math.min(minn, f[i][k] + f[k + 1][j]);
}
f[i][j] = minn;
}
}
}
return f[0][n - 1];
};
java 解法, 执行用时: 10 ms, 内存消耗: 42.4 MB, 提交时间: 2023-06-02 09:45:17
class Solution {
public int strangePrinter(String s) {
int n = s.length();
int[][] f = new int[n][n];
for (int i = n - 1; i >= 0; i--) {
f[i][i] = 1;
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
f[i][j] = f[i][j - 1];
} else {
int minn = Integer.MAX_VALUE;
for (int k = i; k < j; k++) {
minn = Math.min(minn, f[i][k] + f[k + 1][j]);
}
f[i][j] = minn;
}
}
}
return f[0][n - 1];
}
}
cpp 解法, 执行用时: 56 ms, 内存消耗: 9.2 MB, 提交时间: 2023-06-02 09:45:03
class Solution {
public:
int strangePrinter(string s) {
int n = s.length();
vector<vector<int>> f(n, vector<int>(n)); // f[i][j] 打印完区间[i, j]最少操作数
for (int i = n - 1; i >= 0; i--) {
f[i][i] = 1;
for (int j = i + 1; j < n; j++) {
if (s[i] == s[j]) {
f[i][j] = f[i][j - 1];
} else {
int minn = INT_MAX;
for (int k = i; k < j; k++) {
minn = min(minn, f[i][k] + f[k + 1][j]);
}
f[i][j] = minn;
}
}
}
return f[0][n - 1];
}
};
python3 解法, 执行用时: 436 ms, 内存消耗: 16.2 MB, 提交时间: 2023-06-02 09:41:57
# 与 312思想基本一致，枚举 k 时加一层限制
class Solution:
def strangePrinter(self, s: str) -> int:
if not s: return 0
N = len(s)
dp = [[0]*(N) for i in range(N+1)]
for l in range(N): # 区间长度
for i in range(N-l): # 区间起点
j = i + l # 区间终点
dp[i][j] = dp[i+1][j] + 1 # 初始化
for k in range(i+1, j+1): # 枚举分割点
if s[k] == s[i]: # 首位一样可减少一次
dp[i][j] = min(dp[i][j], dp[i][k-1]+dp[k+1][j])
return dp[0][-1]