Interleave strings

The best way is to use dynamic programing. Here is an example: The two short strings are b="daba" and a="cbaa", and the long string is "dabacbaa". They are indexed 1 strings. We start from the last elements.

• Step1. Both a[4] and b[4] matches the element c[8], so the true/false grid [4,4] depends on its two neighbors, [4,3] and [3,4]. 

• Step2. For grid[4,3], a[4] matches c[7], so dependency goes up to [3,3]. 
• For grid[3,4], both a[3] and b[4] matches c[7], so dependency goes to two neighbors:[2,4] and [3,3] 

• Step3. For grid[3,3], b[3] matches c[6], so go left to [3,2]
• For gird [2,4], a[2] matches c[6], so go up to [1,4]

• Step4. For grid[3,2], no matches to c[5], halt (mark false)
• For grid[1,4], a[1] matches c[5], go up to [0,4]

• Step5-9. [0,4]->[0,3]->[0,2]->[0,1]->[0,0]

Grid [0,0] is the only true cell for base case, pass along the dependency and
we find out that [4,4] is true.
Link to the C++ code

/**Update 12/01/2012. This solution is not correct.

85 Answers
Three strings say A,B,C are given to you. Check weather 3rd string is 
interleaved from string A and B.
Ex: A="abcd" B="xyz" C="axybczd". answer is yes. o(n)

- learn on August 27, 2012 in United States | Report Duplicate 
*/

/**Hints from the comments.
Simple case: pointers to A,B,C are pA,pB,pC. Compare pA (or pB) agains 
pC, if matches, ++pA (or ++pB) if none of pA or pB matches, return false

Duplication case: if pA and pB points to the same character, we call it 
a conflict. The conflict character is pushed into a FIFO queue, and do 
both ++pA and ++pB. When a non-conflict character appears, register it,
pA, for example. Keep searching until pA does not match the next character,
then you HAVE TO consider the conflict queue before using pB.

The queue should have a higher priority than pA/pB, since the queue stores
elemenens BEFORE the pointers.

When the queue is not empty, the match process switching between pA and pB
are forbidden. Since if pA is in process, the queue equivalently stores 
elements BEFORE current pB, so skipping the queue directly to pB 
is not allowed.
*/

#include <string>
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
class Solution{
public:
  bool isInterleave(string const& A, string const& B, string const& C){
    if (C.length()!= A.length() + B.length()) return false;
    deque<int> conflict_que;
    int conflict_flag = 0;
    for(int aii = 0, bii = 0, cii = 0; cii < C.length(); ++cii){
      if (!conflict_que.empty() && conflict_que.front() == C[cii]){
        conflict_que.pop_front();
        continue;
      }//conflict_que has a match
      if (A[aii] == B[bii]){
        if (A[aii] == C[cii]){
          ++aii; ++bii; conflict_flag = 0;
          conflict_que.push_back(A[aii]);
          continue;
        } else return false;//A==B, but no match for C
      } else if (A[aii] == C[cii]){
        if (!conflict_que.empty() && conflict_flag == 2) return false;
        //attemp to jump over conflict_que from B
        ++aii; conflict_flag = 1;
        continue;
      } else if (B[bii] == C[cii]){
        if (!conflict_que.empty() && conflict_flag == 1) return false;
        ++bii; conflict_flag = 2;
        continue;
      } else return false;//no match at all, check queue
    }//for cii
    return true;
  }//isInterleave
};

int main(){
  cout<< "Hello"<<endl;
  string A("aaa");
  string B("abc");
  string C("aabcaa");
  Solution s;
  bool result = s.isInterleave(A,B,C);
  cout << result <<endl;
  A = "abcd"; B ="xyz"; C = "axybczd";
  result = s.isInterleave(A,B,C);
  cout<< result <<endl;
  return 0;
}