Edit Distance — Solution & Editorial

Back to the Problem

dp[i][j] = min(delete, insert, substitute-or-match); border row/column are i and j. Rolling one row keeps memory linear.

Complexity: O(|A|·|B|)