0
$\begingroup$

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;
}
$\endgroup$
  • $\begingroup$ Reverse both strings and apply their algorithm. You have just switched "back" and "start" without changing your problem one bit. $\endgroup$ – Yuval Filmus Jan 10 at 14:34
  • $\begingroup$ @YuvalFilmus It's like using their algo. I mean to say that I want such algo that can recursively perform the operation from the start of the string and recursively sending the first k or any specific no. of characters from both strings and searching this out. What you say simply uses the same algo. $\endgroup$ – jay Jan 10 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.