编辑距离
编辑距离定义：
编辑距离,也叫莱文斯坦距离(Levenshtein Distance),是针对二个字符串（例如英文字）的差异程度的量化量测，量测方式是看至少需要多少次的处理才能将一个字符串变成另一个字符串。
题目 input： str1 = "abc" str2 = "yabd"
题目描述：
给出两个字符串，求出最小的编辑距离，从str1 转换到 str2。每个字符总共有三个转换操作：插入，删除，替换。
如图所示，题目给出的例子的结果是2，如果需要将str1 转换乘 str2， 我们可以看到，我们需要在字符串 abc 面前插入一个字符 y，同时需要将字符串abc的c替换成字符d。这总共是执行了两步操作。所以结果2。
解决思路：
1. 画二维图（转换成python就是一个二维数组）
画一个二维图去计算每一个字符需要转换乘对应字符所需要的距离是多少，注意：每个字符串前面都会有一个空字符。中间的空白空格需要填写的是，从str1中的一个子字符串 转换到 str2的一个子字符串的最小的编辑。
2. 填写编辑距离
说明： 图中的位置我会用坐标来表示（0，0），（1，0）代表坐标的意思，黑色数字代表编辑距离
首先我们先从 行 开始，
第二行的空字符串准换到，第二列的空字符串是相等的，所以我们既不用 插入操作，也不用删除操作，也不用替换操作，就能转换到另一个。所以编辑距离是0。
再从这个空字符串转换到 “ ” y 我们需要几步呢？ 在空字符串添加里面加上一个“ ” y 我们就转化成了“ ” y，我们执行了一个 添加 的操作，所以编辑距离是1。
如果我们需要从空字符串转换到 “ ” y a 我们需要几步呢？在字符串 “ ” y 的基础上再加一个 a 我们就得到了 " " y a， 所以我们又执行了一个 添加 操作，所以编辑距离在上一个添加的操作的基础上增加了一个 1，总共是2，后面的以此类推。
然后我们开始看 列
第三行的 ” “ a 转换到 ” “ 我们需要执行什么操作？删除！，我们需要移除 a ，所以我们执行一次移除的操作，因此编辑距离 + 1，0 + 1 = 1，所以编辑距离是1。下面的以此类推，” “ a b 转换到 ” “ 我们需要执行两次移除操作，所以总共是 2 。。。
我们继续填写
我们看到坐标（1，-1）最小的编辑距离是1，” “ a 转换到 ” “ y 我们只需要将 a 替换成 y。但是我们也可以先移除 （0，-1）a 坐标， 然后增加（1，0）一个 y，这样的编辑距离是2。但是我们需要填入的是最小编辑距离，所以最终我们填入1。
然后我们移动到坐标（2，-1）我们可以看到这里的编辑距离是1，” “ a 转换到 ” “ y a 我们需要添加一个 y。如图中绿色字的部分，因为a 和 a是相同的，所以我们消除它，然后我们可以发现字符串只剩下了 str1 = “ ”，str2 = " " y，所以str1 到 str2 只需要 添加 y。所以编辑距离是1。
（3， -1）的编辑距离我们可以理解成：“ ” a 在转成 “ ” y a 的基础上插入了一个 字符b，所以可以看成是在 “ ” a 转成 “ ” y a的基础上加一个1，所以我们可以看出“ ” a转成 “ ” y a b 的编辑距离是 1 + 1 = 2。后面的d也可以这样理解，在 “ ” y a b 的基础上再新增一个 1，所以（4， -1) 的编辑距离是3。
因此我们发现这个编辑距离填写的规律，如下图所示坐标（3，-1）的编辑距离是它 上方，左上方，左边的最小数 + 1（在两个字符不一样的情况下。坐标（4， -1） 同理 min(上方，左上方，左边）= min(4, 3, 2) = 2， 因此（4， -1）的编辑距离等于 2 + 1 = 3。但是在两个字符串一样的情况，如（2， -1），a 和 a是相同的所以不需要 +1，所以（2，-1）处的编辑距离 = min（2，1，1）= 1。接下来的方框大家都会填了吧？
最后是最终的二维表的所有编辑距离，我们最终的答案是取最右下角的数字，也就是2，所以我们最终的答案是2。
最后补充一点，左上角的编辑距离总是三个数中最小的
时间复杂度分析：
O(nm) time，因为你要建立的是一个str1+1行 和 str2+1列的二维数组，并且填写里面每一个元素，并返回最后一个元素，所以程序的时间复杂度是和程序输入str1和str2长度有关。
空间复杂度分析：
我们需要开辟一个str1+1行 和 str2+1列的二维数组取存储我们的编辑距离，所以我们的空间复杂度也是O(nm)，当然还有优化的空间。
3. 代码
接下来我们进入代码环节
这次代码同样也分成了，有注释和和没有注释的版本，没有注释的请拉到最底部
第六行代码生成list中的第一行是
[0,1,2,3,4,....] 因为空字符转换乘其他非空字符串就是一直加加加
列也同样是0,1,2,3,4.... 列和行的长度和输入的str1 str2的长度有关
没有注释的版本
恭喜你看到了这里！
接下来我们就来看看如何降低空间复杂度！
我们真的需要把整个n * m的list的空间开辟出来吗？我们最终使用的空间其实是蓝色方框中的部分，我们实际算距离的部分只需要绿色方框和红色方框。所以当我们最终输入的列越短，我们所需要的空间越少。因此我们在处理输入的时候我们可以将比较短的string输入作为我们的列，比较长的则作为我们的行。
所以我们最终的空间复杂度可以是O(min(n, m))
代码：有注释+无注释
无注释
Reference：代码来自Algoexpert，以学习作为主要目的来分享的。
