请实现编辑距离（Levenshtein Distance）算法，并分析其时间与空间复杂度。

回答思路

1. 正确描述状态定义：dp[i][j]表示word1前i个字符到word2前j个字符的编辑距离
2. 写出状态转移方程：插入、删除、替换三种操作取最小值
3. 正确处理边界条件：dp[0][j]=j, dp[i][0]=i
4. 分析时间复杂度为O(m*n)，空间复杂度可优化至O(n)