Printing all the ways to transform S to T.
Recently in a Technical 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)
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<char> 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;
}
I am new to codeforces,sorry if i have done some terrible formatting :|