資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會研究
時尚研究
法律研究C++中的字串交織
假設我們有三個字串 s1、s2 和 s3。然後檢查 s3 是否由 s1 和 s2 交織而成。因此，如果字串為“aabcc”，s2 = “dbbca”，s3 為“aadbbcbcac”，則結果將為真。
為了解決這個問題，我們將按照以下步驟進行 −
定義一個名為 solve() 的方法，該方法將獲取 s1、s2、s3 和一個 3D 陣列 dp，然後獲取 i、j、k
如果 i = 0 且 j = 0 且 k = 0，則返回真
如果 dp[i, j, k] 不為 -1，則返回 dp[i, j, k]
ans := 假
如果 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)
示例
讓我們看下面的實現來獲得更好的理解 −
#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
更新日期： 2020-5-26
375 次瀏覽
廣告