I had to implement a function for getting the Levenshtein distance of two strings for a problem. It linked to the Wikipedia Article for Levenshtein distance and mentioned I can use the dynamic programming solution. Following is my implementation.
def levenshtein_distance(s, t): m, n = len(s) + 1, len(t) + 1 d = [ * n for _ in range(m)] for i in range(1, m): d[i] = i for j in range(1, n): d[j] = j for j in range(1, n): for i in range(1, m): substitution_cost = 0 if s[i - 1] == t[j - 1] else 1 d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + substitution_cost) return d[m - 1][n - 1]
This function did work and my code passed the test case but I'm not sure if this is the most optimum solution.
Any pointers or suggestions will be appreciated.