spider68

Interleaved Strings

Jun 30th, 2020
188
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.89 KB | None | 0 0
  1. bool isInterleave(string A, string B, string C)
  2. {
  3.     int i,j,m=A.length(),n=B.length();
  4.     int dp[m+1][n+1];
  5.     memset(dp,0,sizeof(dp));
  6.     for(i=0;i<=m;i++)
  7.     {
  8.         for(j=0;j<=n;j++)
  9.         {
  10.             if(i==0&&j==0)dp[i][j]=1;
  11.             else if(i==0)
  12.             {
  13.                 if(B[j-1]==C[j-1])dp[i][j]=dp[i][j-1];
  14.             }
  15.             else if(j==0)
  16.             {
  17.                 if(A[i-1]==C[i-1])dp[i][j]=dp[i-1][j];
  18.             }
  19.             else if(A[i-1]==C[i+j-1]&&B[j-1]!=C[i+j-1])
  20.             {
  21.                 dp[i][j]=dp[i-1][j];
  22.             }
  23.             else if(A[i-1]!=C[i+j-1]&&B[j-1]==C[i+j-1])
  24.             {
  25.                 dp[i][j]=dp[i][j-1];
  26.             }
  27.             else if(A[i-1]==C[i+j-1]&&B[j-1]==C[i+j-1])
  28.             {
  29.                 dp[i][j]=dp[i-1][j]||dp[i][j-1];
  30.             }
  31.         }
  32.     }
  33.     return dp[m][n];
  34. }
Add Comment
Please, Sign In to add comment