package main

func minDistance(word1 string, word2 string) int {
	// A classic dp problem. Assume that dp[i][j] is the steps
	// that needs to be taken to change w1[0...i-1] into w2[0...j-1],
	// then we have dp[i][0] = i (i steps to change len i str into ""),
	// and dp[0][j] = j. If we known dp[i-1][j-1], then:
	// 1) if w1[i-1] == w2[j-1], dp[i][j] = dp[i-1][j-1];
	// 2) if not equal, w1[0...i-1]->w2[0...j-2]->(insert w2[j-1])
	//    dp[i][j] = dp[i][j-1] + 1
	// 3) or (delete w1[i-1])->w1[0...i-2]->w2[0...j-1]
	//    dp[i][j] = dp[i-1][j] + 1
	// 4) or (replace w1[i-1] with w2[j-1])->w1[0...i-2]+w2[j-1]->w2[0...j-2]+w2[j-1]
	//    dp[i][j] = dp[i-1][j-1] + 1
	m, n := len(word1), len(word2)
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
		dp[i][0] = i
	}
	for i := 1; i <= n; i++ {
		dp[0][i] = i
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if word1[i-1] == word2[j-1] {
				dp[i][j] = dp[i-1][j-1]
			} else {
				dp[i][j] = minInts(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
			}
		}
	}
	return dp[m][n]
}

// func main() {
// 	println(minDistance("", ""))
// 	println(minDistance("horse", "ros"))
// }