从字符串 A 中删除字符以移除任何作为字符串 B 的子序列的最小成本

给定两个字符串 string A 和 string B，以及一个数组表示删除给定字符串 A 的第 i 个字符的成本。我们需要以最小成本删除字符串 A 的一些字符（可能为零或没有），以使 A 的任何子序列都不表示字符串 B。我们将看到三种实现代码的方法：递归方法；递归和备忘录方法；以及表格化或迭代动态规划。

示例

让我们来看下面的例子：

输入

string a = "xanxd"
string b = "xd" 
int cost[] = {1, 2, 3, 4, 5}

输出

5

解释

这里我们需要从字符串 A 中删除所有出现的“xd”作为子序列，为此我们有两种方法：我们可以从给定字符串中删除“d”，这将导致成本为 5；或者我们必须删除两者“x”，这又将花费 1 + 4，即 5。

递归方法

在这种方法中，我们将创建一个递归函数，该函数将采用两个字符串的当前索引和两个字符串作为参数，以及第二个字符串中删除的索引数。将有两种不同的情况，并且两者都分别处理。

如果两个字符串在任何位置的当前字符相同，那么我们必须决定是删除字符串 A 的当前字符（给定成本），还是跳过它，并且不会更改已删除的变量。

如果两个字符不同，则不需要删除，我们将直接移动到字符串 A 的下一个字符。

示例

Open Compiler
#include <bits/stdc++.h>
using namespace std;

// recursive function to get the required result 
int rec(string& a, string& b, int idx1, int idx2, vector<int>& cost, int rem){
   // base condition to check the edge cases 
   if(idx1 == 0 or idx2 == 0) {
      return rem == 0 ? 1e5:0;
   }	
   if(a[idx1 - 1] == b[idx2 - 1]){
      return min(cost[idx1-1] + rec(a,b, idx1-1, idx2, cost, rem), rec(a, b, idx1-1, idx2-1, cost, rem-1));
   } else {
      return rec(a, b, idx1-1, idx2, cost, rem);
   }
}
// function to get call to the recursive function 
int getCost(string a, string b, vector<int> cost){
   // calling to the recursive function 
   return rec(a, b, a.length(), b.length(), cost, b.length());
}
int main(){
   string a = "abccdabccdabccd"; // given string a
   string b = "bccd"; // given string b
   vector<int> cost = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }; // given cost array    
   // calling to the function to get the result
   cout << "Minimum cost to delete characters from String A to remove any subsequence as String B is: " << getCost(a, b, cost);
   return 0;
}

输出

Minimum cost to delete characters from String A to remove any subsequence as String B is: 21

时间和空间复杂度

上述代码的时间复杂度为 O(2^M)，其中 M 是给定第二个字符串的大小。

上述代码的空间复杂度为 O(M)，因为我们正在进行递归调用，并且递归栈会占用内存。

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

递归 + 备忘录方法

在这种方法中，我们将存储函数调用中已访问状态的结果，并且对于再次调用该函数，将返回该值，这将时间复杂度从指数减少到二次。让我们看看代码以便更好地理解：

示例

Open Compiler
#include <bits/stdc++.h>
using namespace std;

int memo[105][105][3]; // array to store results 
// recursive function to get the required result 
int rec(string& a, string& b, int idx1, int idx2, vector<int>& cost, int rem){
   // base condition to check the edge cases 
   if(idx1 == 0 or idx2 == 0) {
      return rem == 0 ? 1e5:0;
   }	
   int state = rem > 0 ? 1 : 0;
   if(memo[idx1][idx2][state] != -1){
      return memo[idx1][idx2][state]; 
   }
   if(a[idx1 - 1] == b[idx2 - 1]){
      memo[idx1][idx2][state] = min(cost[idx1-1] + rec(a,b, idx1-1, idx2, cost, rem), rec(a, b, idx1-1, idx2-1, cost, rem-1));
      return memo[idx1][idx2][state]; 
   } else {
      memo[idx1][idx2][state] = rec(a, b, idx1-1, idx2, cost, rem);
      return memo[idx1][idx2][state]; 
   }
}
// function to get call to the recursive function 
int getCost(string a, string b, vector<int> cost){
   memset(memo, -1, sizeof(memo));
   // calling to the recursive function 
   return rec(a, b, a.length(), b.length(), cost, b.length());
}
int main(){
   string a = "abccdabccdabccd"; // given string a
   string b = "bccd"; // given string b
   vector<int> cost = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }; // given cost array   
   // calling to the function to get the result
   cout << "Minimum cost to delete characters from String A to remove any subsequence as String B is:" << getCost(a, b, cost);
   return 0;
}

输出

Minimum cost to delete characters from String A to remove any subsequence as String B is: 21

时间和空间复杂度

上述代码的时间复杂度为 O(N*M)，其中 M 是给定第二个字符串的大小，N 是第一个字符串的大小。

上述代码的空间复杂度为 O(N*M)，因为我们使用的是一个 3 维数组（大约为 N*M 大小）。

结论

在本教程中，我们实现了一个问题，以查找从给定字符串 A 中删除字符以移除任何作为给定字符串 B 的子序列的最小成本。其中字符串 A 的每个字符的成本也给出。首先，我们实现了一种递归方法，然后我们将其更新为一种备忘录方法，其中我们存储已访问状态的结果并存储在一个数组中以减少时间复杂度。

更新于：2023年8月24日

178 次浏览

开启您的职业生涯

完成课程获得认证

开始
广告