Medium

题目描述

给定一个长度为 n 的字符串 source，一个字符串 pattern（它是 source 的子序列），以及一个排序的整数数组 targetIndices，其中包含范围 [0, n - 1] 内的不同数字。

我们定义一个操作为从 source 的索引 idx 处删除一个字符，满足以下条件：

  • idx 是 targetIndices 的一个元素
  • 删除字符后，pattern 仍然是 source 的子序列

执行操作不会改变 source 中其他字符的索引。例如，如果你从 “acb” 中删除 ‘c’，索引 2 处的字符仍然是 ‘b’。

返回可以执行的最大操作数。

示例 1：

输入：source = "abbaa", pattern = "aba", targetIndices = [0,1,2]
输出：1
解释：我们不能删除 source[0]，但可以执行以下两个操作之一：
- 删除 source[1]，使得 source 变成 "a_baa"
- 删除 source[2]，使得 source 变成 "ab_aa"

示例 2：

输入：source = "bcda", pattern = "d", targetIndices = [0,3]
输出：2
解释：我们可以在两次操作中删除 source[0] 和 source[3]。

示例 3：

输入：source = "dda", pattern = "dda", targetIndices = [0,1,2]
输出：0
解释：我们不能从 source 中删除任何字符。

示例 4：

输入：source = "yeyeykyded", pattern = "yeyyd", targetIndices = [0,2,3,4]
输出：2
解释：我们可以在两次操作中删除 source[2] 和 source[3]。

约束条件：

  • 1 <= n == source.length <= 3 * 10³
  • 1 <= pattern.length <= n
  • 1 <= targetIndices.length <= n
  • targetIndices 按升序排序
  • 输入保证 targetIndices 包含范围 [0, n - 1] 内的不同元素
  • source 和 pattern 只包含小写英文字母
  • 输入保证 pattern 在 source 中作为子序列出现

解题思路

这是一个动态规划问题。我们需要在删除尽可能多的目标字符的同时，确保 pattern 仍然是 source 的子序列。

核心思路：

使用三维动态规划 dp[i][j][k] 表示：考虑 source 的前 i 个字符、pattern 的前 j 个字符、targetIndices 的前 k 个索引时，能够删除的最大字符数。

状态转移：

  1. 对于每个位置 i，我们需要判断当前字符是否可以删除
  2. 如果当前位置在 targetIndices 中，我们有两种选择：
    • 删除该字符（如果删除后仍能保证 pattern 匹配）
    • 不删除该字符
  3. 如果当前位置不在 targetIndices 中，只能保留该字符

关键点：

  • 需要确保删除字符后，剩余的字符仍能匹配 pattern
  • 使用贪心思想：优先删除不影响匹配的字符
  • 通过记忆化搜索或自底向上的DP来避免重复计算

优化思路： 可以使用二维DP优化，其中 dp[i][j] 表示使用 source 前 i 个字符匹配 pattern 前 j 个字符时能删除的最大字符数。

代码实现

class Solution {
public:
    int maxRemovals(string source, string pattern, vector<int>& targetIndices) {
        int n = source.length();
        int m = pattern.length();
        unordered_set<int> targets(targetIndices.begin(), targetIndices.end());
        
        // dp[i][j] = 使用source前i个字符匹配pattern前j个字符时的最大删除数
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));
        dp[0][0] = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= m; j++) {
                if (dp[i][j] == -1) continue;
                
                // 选择1: 如果当前字符在目标索引中，尝试删除
                if (targets.count(i)) {
                    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + 1);
                }
                
                // 选择2: 保留当前字符
                if (j < m && source[i] == pattern[j]) {
                    // 匹配pattern的下一个字符
                    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j]);
                } else if (j == m) {
                    // pattern已经完全匹配
                    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
                }
            }
        }
        
        return dp[n][m];
    }
};

class Solution:
    def maxRemovals(self, source: str, pattern: str, targetIndices: List[int]) -> int:
        n, m = len(source), len(pattern)
        targets = set(targetIndices)
        
        # dp[i][j] = 使用source前i个字符匹配pattern前j个字符时的最大删除数
        dp = [[-1] * (m + 1) for _ in range(n + 1)]
        dp[0][0] = 0
        
        for i in range(n):
            for j in range(m + 1):
                if dp[i][j] == -1:
                    continue
                
                # 选择1: 如果当前字符在目标索引中，尝试删除
                if i in targets:
                    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + 1)
                
                # 选择2: 保留当前字符
                if j < m and source[i] == pattern[j]:
                    # 匹配pattern的下一个字符
                    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j])
                elif j == m:
                    # pattern已经完全匹配
                    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
        
        return dp[n][m]

public class Solution {
    public int MaxRemovals(string source, string pattern, int[] targetIndices) {
        int n = source.Length;
        int m = pattern.Length;
        HashSet<int> targets = new HashSet<int>(targetIndices);
        
        // dp[i][j] = 使用source前i个字符匹配pattern前j个字符时的最大删除数
        int[,] dp = new int[n + 1, m + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i, j] = -1;
            }
        }
        dp[0, 0] = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= m; j++) {
                if (dp[i, j] == -1) continue;
                
                // 选择1: 如果当前字符在目标索引中，尝试删除
                if (targets.Contains(i)) {
                    dp[i + 1, j] = Math.Max(dp[i + 1, j], dp[i, j] + 1);
                }
                
                // 选择2: 保留当前字符
                if (j < m && source[i] == pattern[j]) {
                    // 匹配pattern的下一个字符
                    dp[i + 1, j + 1] = Math.Max(dp[i + 1, j + 1], dp[i, j]);
                } else if (j == m) {
                    // pattern已经完全匹配
                    dp[i + 1, j] = Math.Max(dp[i + 1, j], dp[i, j]);
                }
            }
        }
        
        return dp[n, m];
    }
}

var maxRemovals = function(source, pattern, targetIndices) {
    const n = source.length;
    const m = pattern.length;
    const targetSet = new Set(targetIndices);
    
    // dp[i][j] = max removals using first i chars of source to match first j chars of pattern
    const dp = Array(n + 1).fill(null).map(() => Array(m + 1).fill(-Infinity));
    dp[0][0] = 0;
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j <= Math.min(i, m); j++) {
            if (dp[i][j] === -Infinity) continue;
            
            // Try to remove current character if it's in targetIndices
            if (targetSet.has(i)) {
                dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j] + 1);
            }
            
            // Keep current character
            dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j]);
            
            // Use current character to match pattern if possible
            if (j < m && source[i] === pattern[j]) {
                dp[i + 1][j + 1] = Math.max(dp[i + 1][j + 1], dp[i][j]);
            }
        }
    }
    
    return dp[n][m];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数值说明
时间复杂度O(n × m)n 为 source 长度，m 为 pattern 长度，需要填充 DP 表
空间复杂度O(n × m)DP 表的空间开销

相关题目