Your question is Edit Distance Algorithm. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
Demandbase One may need to compare slightly different account or contact names during matching. Given two strings, compute their Levenshtein edit distance, the minimum number of single-character operations needed to transform the first string into the second.
Allowed operations are inserting one character, deleting one character, or replacing one character. Each operation has cost 1, and matching characters have cost 0.
Implement edit_distance(word1, word2). The inputs are strings containing lowercase English letters. Return an integer representing the minimum edit cost. The function must use dynamic programming and should use O(min(m, n)) auxiliary space, where m and n are the input lengths.
def edit_distance(word1, word2):