C ++中的交织字符串

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有三个字符串s1，s2和s3。然后检查是否通过交错s1和s2形成s3。因此，如果字符串是“ aabcc”，s2 =“ dbbca”，而s3是“ aadbbcbcac”，则结果为true。

为了解决这个问题，我们将遵循以下步骤-

  • 定义一个称为的方法solve()，它将采用s1，s2，s3和一个3d数组dp，然后是i，j，k

  • 如果i = 0和j = 0且k = 0，则返回true

  • 如果dp [i，j，k]不为-1，则返回dp [i，j，k]

  • 回答：=假

  • 如果j> 0且k> = 0且s2 [j] = s3 [k]，则

    • ans：= solve（s1，s2，s3，dp，i – 1，j，k – 1）

  • 如果j> 0且k> = 0且s2 [j] = s3 [k]，则

    • ans：= ans ORsolve（s1，s2，s3，dp，i，j – 1，k – 1）

  • 设置dp [i，j，k]：= ans

  • 返回dp [i，j，k]

  • 从主要方法中，执行以下操作-

  • n：= s1的大小，m：= s2的大小，o：= s3的大小

  • 在s1，s2，s3之前添加一个空格。

  • 制作一个大小为（n + 1）x（m + 1）x（o + 1）的数组，并用-1填充

  • 返回solve(s1,s2,s3,dp,n,m,o)

示例

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool solve(string s1, string s2, string s3, vector < vector < vector <int>>>& dp, int i, int j, int k){
      if(i ==0 && j == 0 && k == 0)return true;
      if(dp[i][j][k] !=-1)return dp[i][j][k];
      bool ans = false;
      if(i > 0 && k >= 0 && s1[i] == s3[k]){
         ans = solve(s1, s2, s3, dp, i - 1, j, k - 1);
      }
      if(j >0 && k >=0 && s2[j] == s3[k]){
         ans |= solve(s1, s2, s3, dp, i, j - 1, k - 1);
      }
      return dp[i][j][k] = ans;
   }
   bool isInterleave(string s1, string s2, string s3) {
      int n = s1.size();
      int m = s2.size();
      int o = s3.size();
      s1 = " " + s1;
      s2 = " " + s2;
      s3 = " " + s3;
      vector < vector < vector <int>>> dp(n + 1, vector < vector <int>>(m + 1, vector <int> (o + 1, -1)));
      return solve(s1, s2, s3, dp, n , m , o );
   }
};
main(){
   Solution ob;
   cout << (ob.isInterleave("aabcc", "dbbca", "aadbbcbcac"));
}

输入项

"aabcc", "dbbca", "aadbbcbcac"

输出结果

1

以上是 C ++中的交织字符串 的全部内容， 来源链接： utcz.com/z/316491.html

回到顶部