C++에서 문자열 인터리빙

세 개의 문자열 s1, s2 및 s3이 있다고 가정합니다. 그런 다음 s1과 s2를 인터리빙하여 s3이 구성되었는지 확인합니다. 따라서 문자열이 "aabcc", s2 ="dbbca", s3이 "aadbbbcbcac"이면 결과는 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]
를 반환합니다.
as :=거짓
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"

C++에서 문자열 인터리빙

예시

입력

출력