Here is another GeeksforGeeks problem that asks how to find the shortest Uncommon Subsequence of 2 strings?
For example,
Input : S = “babab” T = “babba”
Output : 3
The subsequence “aab” of length 3 is present in S but not in T.
Input : S = “abb” T = “abab”
Output : -1
There is no subsequence that is present in S but not in T.
Can anyone explain this stuff with respect to recursively going from the start of the string rather than their from the back of the strings?
I think for the recursive solution, they have started from the back
of both strings and then recursively gone to the start.
Can anyone transform this to start the recursion from the start
of the strings and then go on until the end of the strings?
Later, I'll then try myself the DP solution out of it.
I'm unable to get their logic but tried it my way to write the code.
Here, is the partial solution written by me (which doesn't makes sense to me too) which isn't working but I want the solution in this form. ie - to send the first parts of both the string and not from their end parts.
Help me in correcting it. Please do mention the explanation for the developed code.
#include<iostream>
using namespace std;
typedef int ll;
ll fun(string s,string t,ll a,ll b){
if(a>=s.length()){
if(b==0){
return 999999;
}
else{
return 0;
}
}
if(b>=t.length()){
if(a==0){
return 999999;
}
else{
return 0;
}
}
ll flag=0;
ll i=0;
for(i=0;i<b;++i){
if(s[a]==t[i]){
flag=1;
//cout<<"->"<<s[a]<<" "<<t[i]<<endl;
break;
}
}
if(flag==0){
return 1;
}
return min(1+fun(s,t,a+1,i+1),fun(s,t,a+1,i));
}
int main(){
string s;s="sa";//cin>>s;
string t;t="as";//cin>>t;
ll b=fun(s,t,0,0);
if(b>=999999){
cout<<-1;
}
else{
cout<<b;
}
return 0;
}