Hello! Today we’ll looking at how to determine
if string s1 is a subsequence of s2
This can be easily solved by DP-LCS. Notice that the Longest Common Subsequence(LCS) would give the common subsequence of s1 and s2 with the maximum length. To see if s1 is a subsequence of s2, check if LCS(s1,s2)==s1 or length(LCS(s1,s2))==length(s1).
For example, LCS(“ab”,”awerb”) would give “ab”. The code implementation is straight-forward.
Time Complexity: O(n*m)
