Interleaving String ใน C++

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

ขั้นตอนการแก้ปัญหา

• กำหนดเมธอด 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]
• ans := false
• ถ้า 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 OR solve(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)

ตัวอย่างโค้ด C++

#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);
    }
};

int main(){
    Solution ob;
    cout << (ob.isInterleave("aabcc", "dbbca", "aadbbcbcac"));
}

อินพุต

"aabcc", "dbbca", "aadbbcbcac"

เอาต์พุต

1