112: Longest common subsequence

Даны две строки, верните наибольшую общую подпоследовательность данных строк

 

Пример 1

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

Output:  ACD

Пример 2

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

Output:  ABCT