The   shortest common supersequence   is a problem closely related to the   longest common subsequence,   which you can use as an external function for this task.



Task

Given two strings 



u


{\displaystyle u}

 and 



v


{\displaystyle v}

, find the shortest possible sequence 



s


{\displaystyle s}

, which is the shortest common super-sequence of 



u


{\displaystyle u}

 and 



v


{\displaystyle v}

 where both 



u


{\displaystyle u}

 and 



v


{\displaystyle v}

 are a subsequence of 



s


{\displaystyle s}

. Defined as such, 



s


{\displaystyle s}

 is not necessarily unique.

Demonstrate this by printing 



s


{\displaystyle s}

 where 



u
=


{\displaystyle u=}

“abcbdab” and 



v
=


{\displaystyle v=}

“bdcaba”.



Also see

 Wikipedia: shortest common supersequence 


public class ShortestCommonSupersequence
{
    Dictionary<(string, string), string> cache = new();
 
    public string scs(string x, string y)
    {
        if (x.Length == 0) return y;
        if (y.Length == 0) return x;
 
        if (cache.TryGetValue((x, y), out var result)) return result;
 
        if (x[0] == y[0])
        {
            return cache[(x, y)] = x[0] + scs(x.Substring(1), y.Substring(1));
        }
 
        var xr = scs(x.Substring(1), y);
        var yr = scs(x, y.Substring(1));
        if (yr.Length <= xr.Length)
        {
            return cache[(x, y)] = y[0] + yr;
        }
        else
        {
            return cache[(x, y)] = x[0] + xr;
        }
    }
 
    public static void Main(string[] args)
    {
        var scs = new ShortestCommonSupersequence();
        Console.WriteLine(scs.scs("abcbdab", "bdcaba"));
    }
}
 