116: Edit distance

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2

Only following operations are allowed

Insert a character

Delete a character

Replace a character

Example 1

Input:   word1 = "kitten" word2 = "sitting"

Output:  3

Example 2

Input:   word1 = "intention" word2 = "execution"

Output:  5

Difficulty:Hard

Topic:Dynamic programming

Problem #:116