In: Computer Science
Build a Dynamic Programming algorithm in Python for the following problem.
Given two sequences of vowels, find the length of longest subsequence present in both of them.
NOTE: A subsequence is a sequence that appears in the same order, but not necessarily contiguous. For example, “aei”, “aeo”, “eio”, “aiu”, ... are subsequences of “aeiou”.
Sample Input 1:
aeiou aiu
Sample Output 1:
3
Sample Input 2:
aeaiueoiuaeeoeooaauoi aeuioauuuoaeieeaueuiouaiieuiuuuaoueueauaeiauuo
Sample Output 2:
16
Sample Input 3:
iioioieiaiauaoeoiioiiue iuuueauiaieooaoaaouaaaae
Sample Output 3:
10
Sample Input 4:
iauuieeuuiieiuaeaioaieiaeeuouueaeiuiuuaiioaeuoueuiue oeeiauiiioaieoaouuuiueouauueeiauuiiuueeo
Sample Output 4:
26
Write a program, test using stdin → stdout
def longest_subsequence(first, second, len_1, len_2):
# if current longest is not computed till now
if table[len_1][len_2] == None:
# compute current longest
if len_1 == 0 or len_2 == 0:
longest = 0
# both characters are same
elif first[len_1-1] == second[len_2-1]:
longest = 1 + longest_subsequence(first, second, len_1-1, len_2-1)
# both characters are different
else:
# compute longest subsequence by first taking first element, then second element
temp_1 = longest_subsequence(first, second, len_1, len_2-1)
temp_2 = longest_subsequence(first, second, len_1-1, len_2)
# longest will be maximum of both of above
longest = max(temp_1, temp_2)
# store current longest
table[len_1][len_2] = longest
# return longest subsequence
return table[len_1][len_2]
# read 2 strings of vowels
first, second = input().split()
len_1 = len(first)
len_2 = len(second)
# matrix table for dynamic programming
table = [[None]*(len_2+1) for i in range(len_1+1)]
# print longest common subsequence
print(longest_subsequence(first, second, len_1, len_2))
.
Screenshot:
.
Output:
.