C++ 从字符串A中删除字符来删除字符串B的任何子序列的最小成本

给定两个字符串A和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的下一个字符。

示例

#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)，因为我们在递归调用中使用了递归栈来保存内存。

递归 + 记忆化方法

在这种方法中，我们将存储已经访问过的状态的结果，并在再次调用该函数时返回该值，从而将时间复杂度从指数级降低到二次级。让我们看一下代码以便更好地理解。

示例

#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-D数组（大约为N*M大小）。

结论

在本教程中，我们实现了一个问题，即找到从给定字符串A删除字符的最小成本，以删除任何给定字符串B的子序列。其中，我们还给出了字符串A的每个字符的成本。首先，我们使用递归方法实现，然后我们将其更新为记忆化方法，其中我们存储了访问状态的结果，并将其存储在一个数组中以降低时间复杂度。