Hard

题目描述

有一台奇怪的打印机有以下两个特殊要求：

  • 打印机每次只能打印由同一个字符组成的序列。
  • 每次可以在任意起始和结束位置打印新字符，这会覆盖原有字符。

给你一个字符串 s ，你的任务是计算这个打印机打印它所需的最少打印次数。

示例 1：

输入：s = "aaabbb"
输出：2
解释：首先打印 "aaa"，然后打印 "bbb"。

示例 2：

输入：s = "aba"
输出：2
解释：首先打印 "aaa"，然后在字符串第二个位置打印 "b"，这将覆盖现有字符 'a'。

提示：

  • 1 <= s.length <= 100
  • s 由小写英文字母组成

解题思路

这是一个经典的区间动态规划问题。

基本思路： 设 dp[i][j] 表示打印字符串 s[i...j] 所需的最少打印次数。

状态转移：

  1. 初始化：dp[i][i] = 1，单个字符需要打印 1 次
  2. 转移方程：对于区间 [i, j]，考虑两种策略：
    • 分割策略：在位置 k 处分割，dp[i][j] = min(dp[i][k] + dp[k+1][j])
    • 合并策略：如果 s[i] == s[j]，可以一次性打印首尾字符，然后处理中间部分：dp[i][j] = dp[i][j-1]

关键优化：

  • 当 s[i] == s[j] 时，我们可以将 s[j] 和 s[i] 在同一次打印中完成，这样就不需要额外的打印次数
  • 预处理去除连续相同字符可以优化性能

算法步骤：

  1. 可选择性地预处理字符串，去除连续重复字符
  2. 使用区间DP，枚举所有可能的区间长度
  3. 对每个区间，尝试分割点和合并策略
  4. 返回 dp[0][n-1]

时间复杂度为 O(n³)，空间复杂度为 O(n²)。

代码实现

class Solution {
public:
    int strangePrinter(string s) {
        int n = s.length();
        if (n == 0) return 0;
        
        vector<vector<int>> dp(n, vector<int>(n, 0));
        
        // 初始化：单个字符需要打印1次
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        
        // 按区间长度枚举
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = dp[i][j-1] + 1; // 最坏情况：单独打印s[j]
                
                // 尝试合并策略
                for (int k = i; k < j; k++) {
                    if (s[k] == s[j]) {
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j-1]);
                    }
                }
            }
        }
        
        return dp[0][n-1];
    }
};

class Solution:
    def strangePrinter(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0
        
        dp = [[0] * n for _ in range(n)]
        
        # 初始化：单个字符需要打印1次
        for i in range(n):
            dp[i][i] = 1
        
        # 按区间长度枚举
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                dp[i][j] = dp[i][j-1] + 1  # 最坏情况：单独打印s[j]
                
                # 尝试合并策略
                for k in range(i, j):
                    if s[k] == s[j]:
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j-1])
        
        return dp[0][n-1]

public class Solution {
    public int StrangePrinter(string s) {
        int n = s.Length;
        if (n == 0) return 0;
        
        int[,] dp = new int[n, n];
        
        // 初始化：单个字符需要打印1次
        for (int i = 0; i < n; i++) {
            dp[i, i] = 1;
        }
        
        // 按区间长度枚举
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i, j] = dp[i, j-1] + 1; // 最坏情况：单独打印s[j]
                
                // 尝试合并策略
                for (int k = i; k < j; k++) {
                    if (s[k] == s[j]) {
                        dp[i, j] = Math.Min(dp[i, j], dp[i, k] + dp[k+1, j-1]);
                    }
                }
            }
        }
        
        return dp[0, n-1];
    }
}

var strangePrinter = function(s) {
    const n = s.length;
    const dp = Array(n).fill().map(() => Array(n).fill(0));
    
    for (let len = 1; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;
            if (i === j) {
                dp[i][j] = 1;
            } else {
                dp[i][j] = dp[i][j-1] + 1;
                for (let k = i; k < j; k++) {
                    if (s[k] === s[j]) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j-1]);
                    }
                }
            }
        }
    }
    
    return dp[0][n-1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n³) - 三层循环：区间长度、起始位置、分割点
空间复杂度O(n²) - 二维DP数组存储所有子区间的结果

相关题目