Printing all the ways to transform S to T.
Recently in an Interview,I was asked this question.. Given a String S and another string T,You have to change S to T using following steps only - You can push a character from S to the stack and pop an element from the stack...
Now if a push operation is denoted by 0 and pop is denoted by 1, generate all possible valid strings that can transform S to T.
Given that transformation will always be possible and |S| = |T| <= 15.
For Ex - S = "MADAM" T = "ADAMM" The steps to convert will be - push M (0) push A (0) pop A (1) push D (0) pop D (1) push A (0) pop A (1) push M (0) pop M (1) pop M (1)
So "0010101011" is a valid string,I need to generate all the valid strings.. All i can come up with was this code,which was able to generate a single valid string..Can anyone help me out in how to generate each valid string. (Note: Bitmasking approach is not allowed)
include<bits/stdc++.h>
using namespace std; // i -> upto what position in S we are done // j -> upto what position in T we have completed // o for push //1 for pop bool temp[32] = {0}; stack st; int l = 0,k = 0;
void solve(string& S,string& T,int i,int j) { if(k == 2*l — 1) { for(int i = 0;i <= k;i++) cout << temp[i] << " "; cout << endl; return ; }
if(i < 0 || j < 0 || i > l || j > l)
return;
if(st.size())
if(T[j] == st.top())
{
st.pop();
temp[k++] = 1;
solve(S,T,i,j + 1);
k -= 1;
}
if(T[j] == S[i]) // Both current charcters matches each other
{
st.push(S[i]);
temp[k++] = 0;
st.pop();
temp[k++] = 1;
solve(S,T,i+1,j+1);
k -= 2;
}
if(T[j] != S[i])
{
// Keep pushing characters from S,and increase i until they do not matches
st.push(S[i]);
temp[k++] = 0;
solve(S,T,i+1,j);
k -= 1;
}
}
int main() { ios_base::sync_with_stdio(0); string S,T; cin >> S; cin >> T; // cout << st.top(); l = S.length(); solve(S,T,0,0); return 0; }