Implement function alignStrings in Python

Implement alignStrings in Python

1. Recall that the string alignment problem takes as input two strings x and y, composed of symbols xi,yj E , for a fixed symbol set , and returns a minimal-cost set of edit operations for transforming the string x into string y. Let x contain n, symbols, let y contain niy symbols, and let the set of edit operations be those defined in the lecture notes (substitution, insertion, deletion, and transposition) Let the cost of indel be 1, the cost of swap be 5 (plus the cost of the two sub ops), and the cost of sub be 3, except when x, - yj, which is a "no-op" and has cost 0 In this problem, you will implement and apply three functions (i) alignStrings(x,y) takes as input two ASCII strings r and y, and runs a dynamic programming algorithm to return the cost matrix S, which contains the optimal costs for all the subproblems for aligning these two strings alignStrings(x,y) : // x,y are ASCII strings S - table of length nx+1 by ny+1 // for memoizing the subproblem costs initialize S for i = 1 to nx // fill in the base cases for j - 1 to ny S[i,j] - cost(i,j) // optimal cost for x[0..i] and y[0..j] return S