Edit distance and LCS ( Longest Common Subsequence ) | Python 3 program to find Edit Distance ( when only two operations are allowed , insert and delete ) using LCS . ; Find LCS ; Edit distance is delete operations + insert operations . ; Driver Code
def editDistanceWith2Ops ( X , Y ) : NEW_LINE INDENT m = len ( X ) NEW_LINE n = len ( Y ) NEW_LINE L = [ [ 0 for x in range ( n + 1 ) ] for y 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 ] + 1 NEW_LINE DEDENT else : NEW_LINE INDENT L [ i ] [ j ] = max ( L [ i - 1 ] [ j ] , L [ i ] [ j - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT lcs = L [ m ] [ n ] NEW_LINE return ( m - lcs ) + ( n - lcs ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT X = " abc " NEW_LINE Y = " acd " NEW_LINE print ( editDistanceWith2Ops ( X , Y ) ) NEW_LINE DEDENT