112: Longest common subsequence

Given two strings, return the longest common subsequence of the given strings

 

Example 1

Input:   word1 = "ABCD", word2 = "ACDY"

Output:  ACD

Example 2

Input:   word1 = "ACBCT", word2 = "ABCDAT"

Output:  ABCT