แทรกระหว่างสตริงใน C ++

สมมติว่าเรามีสามสตริง s1, s2 และ s3 จากนั้นตรวจสอบว่า s3 เกิดขึ้นจากการสลับระหว่าง s1 และ s2 หรือไม่ ดังนั้นหากสตริงเป็น “aabcc”, s2 =“dbbca” และ s3 คือ “aadbbcbcac” ผลลัพธ์จะเป็นจริง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

กำหนดวิธีการหนึ่งที่เรียกว่า Solve() ซึ่งจะใช้เวลา s1, s2, s3 และอาร์เรย์ 3 มิติหนึ่งรายการ 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 :=แก้ (s1, s2, s3, dp, i – 1, j, k – 1)
ถ้า j> 0 และ k>=0 และ s2[j] =s3[k] แล้ว
- ans :=ans OR แก้ (s1, s2, s3, dp, i, j – 1, k – 1)
set 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
ผลตอบแทนการแก้ (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"