数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学最小化移除次数，以将另一个字符串作为给定字符串的子序列移除
子序列是指可以从另一个序列中移除零个或多个元素而获得的序列，且不改变剩余元素的顺序。简单来说，子序列是从原始序列中选择元素而保留其相对顺序导出的序列。
例如，考虑序列[1, 2, 3, 4]。这个序列的一些可能的子序列是：[1, 2]，[1, 3, 4]，[2, 4]，[1, 2, 3, 4]，[3]和[4]。
问题陈述
目标是确定要从字符串s1中移除的最小字符数，以便消除s2作为s1中子序列的任何出现。
例如
Input: s1 = “jjkklll”, s2 = “jkl” Output: 2
解释
字符串s1包含子序列“jkl”。为了使s1不包含s2作为子序列，我们可以从s1中移除两个'j'或两个'k'。因此，需要移除的最小字符数为2。
Input: s1 = “”, s2 = “q” Output: 0
解释
由于s1是一个空字符串，因此没有字符需要移除。因此，不需要移除任何字符，因为需要移除的最小字符数为0。
解决方案方法
为了找到需要从字符串s1中移除的最小字符数，以使其不包含字符串s2作为子序列，我们可以使用动态规划方法。其实现如下：
创建一个名为“dp”的二维数组，其维度为NxM，其中N表示字符串s1的长度，M表示字符串s2的长度。此数组将用于存储需要移除的最小字符数。
通过检查s2的第一个字符是否与s1的对应字符匹配来填充dp的第一行。如果匹配，则将dp中的值设置为1，表示需要移除一个字符。
从第二行开始迭代dp的行。对于每一行，迭代列。
如果字符串s1的当前字符与字符串s2的当前字符匹配，我们可以确定需要移除的最小字符数。
计算两个值的最小值：
从dp数组的上一行(i - 1)和当前列(j)移除的最小字符数，并加1。
从dp数组的上一行(i - 1)和上一列(j - 1)移除的最小字符数。
当s1和s2当前位置的字符不匹配时，需要移除的最小字符数与需要从dp数组的上一行(i - 1)和当前列(j)移除的最小字符数相同。
一旦我们迭代了dp数组的所有元素，需要移除的最小字符数将存储在dp[N - 1][M - 1]中，其中N和M分别是字符串s1和s2的长度。
最后，我们可以输出需要从s1中移除的最小字符数，以确保它不包含s2作为子序列。
动态规划方法通过考虑所有可能的组合并在每一步选择最少的移除次数来计算最小字符移除数。
算法
function printMinimumRemovals(s1, s2):
N = length(s1)
M = length(s2)
Create a 2D array dp of size (N) x (M)
// Step 2
For j = 0 to M - 1:
If s1[0] equals s2[j]:
Set dp[0][j] to 1
// Step 3
For i = 1 to N - 1:
For j = 0 to M - 1:
// Step 4
If s1[i] equals s2[j]:
Set dp[i][j] to min(dp[i-1][j] + 1, dp[i-1][j-1])
// Step 5
Else:
Set dp[i][j] to dp[i-1][j]
// Step 6
minimumRemovals = dp[N][M]
// Step 7
print minimumRemovals
function main:
initialise string s1 and s2
function call printMinimumRemovals()
示例：C++程序
给定的代码解决了查找需要从字符串s1中移除的最小字符数以使其成为字符串s2的子序列的问题。该代码使用动态规划来计算此最小移除计数。
printMinimumRemovals函数以两个字符串s1和s2作为输入。它创建一个二维数组dp来存储所需的最小移除次数。在迭代dp的所有元素之后，最少的字符移除数存储在dp[N - 1][M - 1]中。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// This function prints the minimum number of characters that need to be removed from the string `s1` to make it a subsequence of the string `s2`.
void printMinimumRemovals(string s1, string s2){
int N = s1.length();
int M = s2.length();
// Create a 2D array to store the minimum number of characters that need to be removed from the first `i` characters of `` to make it a subsequence of the first `j` characters of `s2`.
vector<vector<int>> dp(N, vector<int>(M));
// Fill the first row of the array.
for (int j = 0; j < M; j++){
// If the first character of `s2` matches the first character of `s1`, then the minimum number of characters that need to be removed is 1.
if (s1[0] == s2[j]){
dp[0][j] = 1;
}
}
// Iterate over the rows of the array.
for (int i = 1; i < N; i++){
// Iterate over the columns of the array.
for (int j = 0; j < M; j++){
// When the current character of s1 matches the current character of s2, the minimum number of characters to be removed is determined by taking the smaller value between two scenarios:
// Removing the minimum number of characters needed to make the first i - 1 characters of s1 a subsequence of the first j characters of s2.
// Removing the minimum number of characters needed to make the first i - 1 characters of s1 a subsequence of the first j - 1 characters of s2.
if (s1[i] == s2[j]){
dp[i][j] = min(dp[i - 1][j] + 1, dp[i - 1][j - 1]);
}
// In case of non-matching characters, consider the minimum number of characters to be removed from the first i - 1 characters of s1 to make it a subsequence of the first j characters of s2.
else{
dp[i][j] = dp[i - 1][j];
}
}
}
// Print the minimum number of characters that need to be removed.
cout << dp[N - 1][M - 1] << endl;
}
int main(){
// Input
string s1 = "bb";
string s2 = "b";
// Function call to obtain the minimum number of character removals.
printMinimumRemovals(s1, s2);
return 0;
}
输出
0
时间和空间复杂度分析
时间复杂度 - O(N*M)
创建大小为NxM的二维向量dp需要O(N*M)的时间。
填充dp的第一行需要O(M)的时间，因为它迭代s2的长度。
迭代dp的行和列的嵌套循环总共需要O(N*M)的时间，因为二维数组的每个元素都被处理一次。
代码的时间复杂度主要由嵌套循环决定，导致整体时间复杂度为O(N*M)。
空间复杂度 - O(N*M)
代码的空间复杂度为O(N + M)，其中N和M分别是字符串s1和s2的长度，因为它取决于输入字符串的大小。
创建大小为NxM的二维向量dp需要O(N*M)的空间。
结论
本文讨论了针对问题陈述的动态规划方法。通过合适的示例解释了问题的概念。解决方案方法包括所涉及的步骤、使用的算法、C++程序实现以及时间和空间复杂度分析。
浏览量：163
