Minimum cost to make two strings identical by deleting the digits | Function to returns cost of removing the identical characters in LCS for X [ 0. . m - 1 ] , Y [ 0. . n - 1 ] ; Following steps build L [ m + 1 ] [ n + 1 ] in bottom up fashion . Note that L [ i ] [ j ] contains cost of removing identical characters in LCS of X [ 0. . i - 1 ] and Y [ 0. . j - 1 ] ; If both characters are same , add both of them ; Otherwise find the maximum cost among them ; Returns cost of making X [ ] and Y [ ] identical ; Find LCS of X [ ] and Y [ ] ; Initialize the cost variable ; Find cost of all acters in both strings ; Driver program to test above function
def lcs ( X , Y , m , n ) : NEW_LINE INDENT L = [ [ 0 for i in range ( n + 1 ) ] for i in range ( m + 1 ) ] NEW_LINE for i in range ( m + 1 ) : NEW_LINE INDENT for j in range ( n + 1 ) : NEW_LINE INDENT if ( i == 0 or j == 0 ) : NEW_LINE INDENT L [ i ] [ j ] = 0 NEW_LINE DEDENT elif ( X [ i - 1 ] == Y [ j - 1 ] ) : NEW_LINE INDENT L [ i ] [ j ] = L [ i - 1 ] [ j - 1 ] + 2 * ( ord ( X [ i - 1 ] ) - 48 ) NEW_LINE DEDENT else : NEW_LINE INDENT L [ i ] [ j ] = max ( L [ i - 1 ] [ j ] , L [ i ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT return L [ m ] [ n ] NEW_LINE DEDENT def findMinCost ( X , Y ) : NEW_LINE INDENT m = len ( X ) NEW_LINE n = len ( Y ) NEW_LINE cost = 0 NEW_LINE for i in range ( m ) : NEW_LINE INDENT cost += ord ( X [ i ] ) - 48 NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT cost += ord ( Y [ i ] ) - 48 NEW_LINE DEDENT ans = cost - lcs ( X , Y , m , n ) NEW_LINE return ans NEW_LINE DEDENT X = "3759" NEW_LINE Y = "9350" NEW_LINE print ( " Minimum ▁ Cost ▁ to ▁ make ▁ two ▁ strings ▁ " , " identical ▁ is ▁ = ▁ " , findMinCost ( X , Y ) ) NEW_LINE