Here is the interview question prompt, presented for reference.

An edit distance is a way to quantify how different two strings are. This is calculated using the minimum number of transformations to turn one string to another.

The transformations include insertion, deletion, and substitution. So when comparing two identical strings, say cat and cat, the edit distance would be 0-- there is only an edit distance where there are differences.

As an example, here's the edit distance for mitten and sitting:

getEditDistance('mitten', 'sitting');
// 3

Here's the rationale for 3 in terms of the transformation steps required:

1. mitten -> sitten (substitution of "s" for "m")
2. sitten -> sittin (substitution of "i" for "e")
3. sittin -> sitting (insertion of "g" at the end).

Can you write a method getEditDistance(a, b) that will return the edit distance?

Constraints

• Length of both the given strings a,b <= 1000
• The answer will always fit in the integer range
• You are only allowed to change one string
• Let m and n be the the lengths of string 1 and string 2, respectively
• Expected time complexity : O(n*m)
• Expected space complexity :O(n*m)

You can see the full challenge with visuals at this link.