[LeetCode]Edit Distance

    仍然是String的题目，自然又想到DP的方法，两个String，二维DP。对于String s和p，[i，j]表示s的前i个char和p的前j个char的最短距离，对于[i，j]，有以下三种情况：

• [i, j] = [i - 1, j - 1] (+ 1)，加一取决于s的第i个和p的第j个match与否，这种情况对应于replace一个字符，或者不需要repalce
• [i , j] = [i - 1,  j] + 1，这种情况对应于插入或者删除s的第i个字符
• [i , j] = [i,  j - 1] + 1，这种情况对应于插入或者删除p的第j个字符

假设输入string分别长m和n，时间复杂度和空间复杂度都是O(m * n)，代码如下：

我们可以用滚动数组把空间优化到O(n)，代码如下：