RECURSION!

I am beginner in recursion so i wanted help from you guys.
Given two strings
a=“bat”
b=“pig”
I want to convert a to b in following way:(changing one character to a to b)

                           bat
                    /       |      \
                pat     bit         bag
              /  \        /    \       /  \
          pit   pag       pit big    pag    big
          |        |      |    |      |        |
       pig      pig       pig  pig    pig     pig

(i also want to print a at every instance)
can u please share code for same and explain it?
THANK YOU!!!

1 Like

Here is my code to do so. I’ve assumed that the strings a and b will always be equal in length.

void rec(string a, string b, vector changed){
for(int i =0;i<a.length();i++){
if(!changed[i]){
char original = a[i];
a[i] = b[i];
changed[i] = true;
rec(a,b,changed);
a[i] = original;
changed[i] = false;
}
}
cout<<a<<’\n’;
}

void solve(){
string a ,b;
cin>>a>>b;
vector< bool > changed(a.length(),false);
rec(a,b,changed);
}
I’ve made a boolean vector ,changed which just tells about the indices which i have changed.
So what i am doing is that for each recursive call i just find an index which is not changed , change it, mark it changed and then pass it to next call. Now in each call i want to change only one index so i undo the changes and mark it unchanged, and look of other unchanged indices.
Finally after the loop print the string.
I hope this makes it clear.

1 Like

Juspay hna :slight_smile:

2 Likes

https://leetcode.com/problems/word-ladder/

2 Likes

I am in third semester right now XD
A friend of mine sent me this…I was confused so i asked here :upside_down_face:
thanks btw

1 Like