docs/Algorithm/Leetcode/Python/072._edit_distance.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 072. Edit Distance 编辑距离\n",
    "\n",
    "### 难度：Hard\n",
    "\n",
    "## 刷题内容\n",
    "\n",
    "> 原题链接\n",
    "\n",
    " - 中文：https://leetcode-cn.com/problems/edit-distance\n",
    " - 英文：https://leetcode.com/problems/edit-distance/\n",
    " \n",
    "> 内容描述\n",
    "\n",
    "```\n",
    "给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。\n",
    "\n",
    "你可以对一个单词进行如下三种操作：\n",
    "\n",
    "插入一个字符\n",
    "删除一个字符\n",
    "替换一个字符\n",
    "\n",
    "示例 1:\n",
    "输入: word1 = \"horse\", word2 = \"ros\"\n",
    "输出: 3\n",
    "解释: \n",
    "horse -> rorse (将 'h' 替换为 'r')\n",
    "rorse -> rose (删除 'r')\n",
    "rose -> ros (删除 'e')\n",
    "\n",
    "示例 2:\n",
    "输入: word1 = \"intention\", word2 = \"execution\"\n",
    "输出: 5\n",
    "解释: \n",
    "intention -> inention (删除 't')\n",
    "inention -> enention (将 'i' 替换为 'e')\n",
    "enention -> exention (将 'n' 替换为 'x')\n",
    "exention -> exection (将 'n' 替换为 'c')\n",
    "exection -> execution (插入 'u')\n",
    "```\n",
    "\n",
    "## 解题方案\n",
    "\n",
    "这个题目是动态规划的典型例题，在 wikipedia 中是有相应页面介绍的。\n",
    "\n",
    " - https://en.wikipedia.org/wiki/Edit_distance#Common_algorithm\n",
    " - https://en.wikipedia.org/wiki/Levenshtein_distance\n",
    "\n",
    "> 思路 1\n",
    "\n",
    " - 使用动态规划\n",
    "\n",
    "下面我们说说，这个题的思路。具体来描述一下。\n",
    "\n",
    "要始终明确一点， dp[i][j] 的含义是使得 word1 的前 i 字符子串与 word2 的前 j 字符子串相等所需要的操作数，这也是为什么我们需要在初始化 dp 矩阵时需要行列数均加上 1 。\n",
    "\n",
    "我们创建一个 dp[][] 二维数组，表示从 word1 的前 i 个字符（下标为：0~ i-1）到 word2 的前 j 个字符（下标为：0~j-1）的编辑过程中，需要的最少步数，那么：\n",
    "\n",
    "如果  $word1[i] = word2[j]$   则   $dp[i][j]   =   dp[i-1][j-1]$\n",
    "\n",
    "如果  $word1[i] != word2[j]$    则   $dp[i][j] =   min   ( dp[i-1][j]  ,  dp[i][j-1],    dp[i-1][j-1] )  + 1$\n",
    "\n",
    "下面就是我们对上述动态规划过程的解释：\n",
    "\n",
    "第一个条件比较容易理解，就是说 word1 的下标为 i 的字符 和 word2 的下标为 j 的字符相同，那么这个位置的字符我们不需要进行操作，所以我们只需要关注 word1 和 word2 去除掉相应位置的字符之后的子串的结果即可。\n",
    "\n",
    "我们下面对第二个条件的三种情况进行重点讲解：\n",
    "\n",
    "假设 word1 的前 i+1 （下标为 0~i）的子串为 \"abcde\"\n",
    "假设 word2 的前 j+1 （下标为 0~j）的子串为 \"abcddgf\"\n",
    "现在 word1[i] != word2[j]，也就是 'e' != 'f'\n",
    "\n",
    "那么我们接下来应该怎么做呢？\n",
    "\n",
    "我们会发现，我们做的三种解释实际上就是把我们题中写到的三种操作模拟在最后一步实现。每种操作都是额外加一的操作。\n",
    "\n",
    "简单说，就是这样：\n",
    " - 1.delete：dp[i-1][j] + 1 —— 保留了从 word1[0~i-1] 转变到 word2[0~j] 的最优操作次数，因为我们的 word1 的 0~i-1 已经能够转变到 word2 了，所以我们就直接把 word1 中的最后一个字符删除掉就行了。所以就需要额外进行一个 删除 操作。\n",
    " - 2.insert：dp[i][j-1] + 1 —— 保留了从 word1[0~i] 转变到 word2[0~j-1] 的最优操作次数，因为我们的 word1 的 0~i 只能转变到 word2 的倒数第二位，所以我们就直接在 word1 的末尾添加一个与 word2 的最后一个字符相同的字符就可以了。所以就需要额外进行一个 插入 操作。\n",
    " - 3.replace：dp[i-1][j-1] + 1 —— 保留了从 word1[0~i-1] 转变到 word2[0~j-1] 的最优操作次数，因为我们的 word1 的 0~i-1 只能转变到 word2 的倒数第二位，而 word1 的最后一位与 word2 的最后一位是不同的，所以现在的情况只需要额外的一个 替换 操作即可。\n",
    "\n",
    "\n",
    "无论我们选取上面 3 中操作的哪种操作，我们选其中最小的值就可以了。\n",
    "\n",
    "参考链接：http://www.cnblogs.com/pandora/archive/2009/12/20/levenshtein_distance.html\n",
    "\n",
    "下面我们看一下代码："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def minDistance(self, word1, word2):\n",
    "        \"\"\"\n",
    "        :type word1: str\n",
    "        :type word2: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 初始化一个 len(word1)+1 * len(word2)+1 的矩阵\n",
    "        matrix = [[i+j for j in range(len(word2) + 1)] for i in range(len(word1) + 1)]\n",
    "        # 辅助理解，matrix 矩阵的样子\n",
    "        # print(matrix)\n",
    "        for i in range(1, len(word1)+1):\n",
    "            for j in range(1,len(word2)+1):\n",
    "                if word1[i-1] == word2[j-1]:\n",
    "                    d = 0\n",
    "                else:\n",
    "                    d = 1\n",
    "                matrix[i][j] = min(matrix[i-1][j]+1, matrix[i][j-1]+1, matrix[i-1][j-1]+d)\n",
    "\n",
    "        return matrix[len(word1)][len(word2)]\n",
    "    \n",
    "s = Solution()\n",
    "word1 = 'horse'\n",
    "word2 = 'ros'\n",
    "print(s.minDistance(word1, word2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面代码的 matrix 矩阵生成，可能会让大家产生理解误差，我在这个地方的理解也是通过大佬问，我才知道具体是怎么回事的。\n",
    "\n",
    "下面我们把它打印一下。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[0, 1, 2, 3],\n",
       "        [1, 2, 3, 4],\n",
       "        [2, 3, 4, 5],\n",
       "        [3, 4, 5, 6],\n",
       "        [4, 5, 6, 7],\n",
       "        [5, 6, 7, 8]])"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "juzhen = [[i+j for j in range(len(word2) + 1)] for i in range(len(word1) + 1)]\n",
    "juzhen = np.mat(juzhen)\n",
    "juzhen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "以 numpy 的样子打印出来，看这样子比较清晰。各行各列对应比较整齐。\n",
    "\n",
    "我要说明的是：\n",
    "\n",
    " - 这个 matrix 的 第 1 行（下标为0的行）的 [0, 1, 2, 3] 这个维度的意思，对应的是 dp[i][j] 。也就是说，word1 取前 i 个字符，然后编辑成 word2 时所需要转换的最少步数。因为这里 i = 0，也就是 word1 取 0 个字符，而 j 我们取 0 - 3 个字符的时候，我们从 word1 变换到 word2 的时候所需要经过的最小步数。本质上，就是在 **空的** word1 上进行对应插入 word2 对应的字符就可以变换到 word2 。word2 取几个字符，我们的最小变换次数就是几。也就对应这个维度上的数字。\n",
    "\n",
    " - 另一个维度上，matrix 的第 1 列（下标为 0 的列），对应的是 [0, 1, 2, 3, 4, 5] 也是对应的 dp[i][j]。只不过我们这里调换了顺序，i 现在不为 0 了，而是 j 为 0 。也就是 word1 取 0~ i 个字符的时候，变换到 word2 的最小步骤数。实际上 word2 是空的，也就是说，我们 word1 有几个字符，我们对应删除几个字符就可以得到 word2 。这就对应着我们的这个列维度上的数字。\n",
    " \n",
    " - 其他维度，i 和 j 都不为 0 的部分，我们的初始化的数字是没有意义的。我们在迭代过程中会全部都更改一遍。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}