fork(26) download
copy 
  1. // A Dynamic Programming based program to check whether a string C is
  2. // an interleaving of two other strings A and B.
  3. #include <iostream>
  4. #include <string.h>
  5. using namespace std;
  6.  
  7. // The main function that returns true if C is
  8. // an interleaving of A and B, otherwise false.
  9. bool isInterleaved(char* A, char* B, char* C)
  10. {
  11.     // Find lengths of the two strings
  12.     int M = strlen(A), N = strlen(B);
  13.  
  14.     // Let us create a 2D table to store solutions of
  15.     // subproblems.  C[i][j] will be true if C[0..i+j-1]
  16.     // is an interleaving of A[0..i-1] and B[0..j-1].
  17.     bool IL[M+1][N+1];
  18.  
  19.     memset(IL, 0, sizeof(IL)); // Initialize all values as false.
  20.  
  21.     // C can be an interleaving of A and B only of sum
  22.     // of lengths of A & B is equal to length of C.
  23.     if ((M+N) != strlen(C))
  24.        return false;
  25.  
  26.     // Process all characters of A and B
  27.     for (int i=0; i<=M; ++i)
  28.     {
  29.         for (int j=0; j<=N; ++j)
  30.         {
  31.             // two empty strings have an empty string
  32.             // as interleaving
  33.             if (i==0 && j==0)
  34.                 IL[i][j] = true;
  35.  
  36.             // A is empty
  37.             else if (i==0 && B[j-1]==C[j-1])
  38.                 IL[i][j] = IL[i][j-1];
  39.  
  40.             // B is empty
  41.             else if (j==0 && A[i-1]==C[i-1])
  42.                 IL[i][j] = IL[i-1][j];
  43.  
  44.             // Current character of C matches with current character of A,
  45.             // but doesn't match with current character of B
  46.             else if(A[i-1]==C[i+j-1] && B[j-1]!=C[i+j-1])
  47.                 IL[i][j] = IL[i-1][j];
  48.  
  49.             // Current character of C matches with current character of B,
  50.             // but doesn't match with current character of A
  51.             else if (A[i-1]!=C[i+j-1] && B[j-1]==C[i+j-1])
  52.                 IL[i][j] = IL[i][j-1];
  53.  
  54.             // Current character of C matches with that of both A and B
  55.             else if (A[i-1]==C[i+j-1] && B[j-1]==C[i+j-1])
  56.                 IL[i][j]=(IL[i-1][j] || IL[i][j-1]) ;
  57.         }
  58.     }
  59.  
  60.     return IL[M][N];
  61. }
  62.  
  63. void test(char *A, char *B, char *C)
  64. {
  65.     if (isInterleaved(A, B, C))
  66.         cout << C <<" is interleaved of " << A <<" and " << B << endl;
  67.     else
  68.         cout << C <<" is not interleaved of " << A <<" and " << B << endl;
  69. }
  70.  
  71.  
  72. // Driver program to test above functions
  73. int main()
  74. {
  75.     char A[15][3][30] =
  76.     {
  77.         {"abcd", "xyz", "axybczd"},
  78.         {"AB", "CD", "CADB"},
  79.         {"AB" ,"CD" ,"CDAB"},
  80.         {"AB" , "A" , "AAB"},
  81.         {"A" ,"AB" ,"ABA"},
  82.         {"A" ,"AB", "BAA"},
  83.         { "ACA" ,"DAS" ,"DAACSA"},
  84.         {"ACA" ,"DAS" ,"DAASCA"},
  85.         {"ACA" ,"DAS", "ADASAC"},
  86.         {"A", "AB" ,"AAB"},
  87.         {"AAB" ,"AAC" ,"AACAAB"},
  88.         {"101", "01", "10011"},
  89.         {"101" ,"01" ,"11010"},
  90.         {"A" ,"C", "CA"},
  91.         {"A", "C", "CD"}
  92.     };
  93.  
  94.     for (int i=0; i<15; ++i)
  95.         test(A[i][0], A[i][1], A[i][2]);
  96.  
  97.         return 0;
  98. }
  99.  
Success #stdin #stdout 0s 2900KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
axybczd is interleaved of abcd and xyz
CADB is interleaved of AB and CD
CDAB is interleaved of AB and CD
AAB is interleaved of AB and A
ABA is interleaved of A and AB
BAA is not interleaved of A and AB
DAACSA is interleaved of ACA and DAS
DAASCA is interleaved of ACA and DAS
ADASAC is not interleaved of ACA and DAS
AAB is interleaved of A and AB
AACAAB is interleaved of AAB and AAC
10011 is interleaved of 101 and 01
11010 is not interleaved of 101 and 01
CA is interleaved of A and C
CD is not interleaved of A and C
https://ideone.com/4jnFZu
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!