^{th}character and prefix of string2 ending with j

^{th}character.

0 <= i <= N and 0 <= j <= M

We fill this table in a bottom-up manner. This is essentially solving the problem by combining the results of it’s sub-problems. (**Dynamic programming**). The entries are filled using the following formula

table[0][i] = i

table[i][0] = i

**Explanation: **

Assume that 0th character is empty, the edit distance between an empty string and a string of length ‘i’ is always ‘i’ because by deleting all the ‘i’ characters, it becomes an empty string.

table[i][j] = table[i-1][j-1] if string1[i] = string2[j]

**Explanation:**

If string1[i] and string2[j] are equal, we don’t need any modifications. Hence it is as same as table[i-1][j-1]

table[i][j] = Min(table[i-1][j],table[i][j-1],table[i-1][j-1]) + 1

**Explanation:**

If string1[i] and string2[j] are not equal, we have three choices.

- Modify the differing character string1[i] to match string2[j]. This requires a cost of table[i-1][j-1] + 1
- Delete string1[i] and try to match the remaining with string2. This requires a cost of table[i-1][j] + 1
- Insert string1[i] into string2. This requires a cost of table[i][j-1] + 1.

Finally table[N][M] contains the required answer.

The time and space complexity for this algorithm is O(n * m).