solution.md

# 编辑距离

<p>给你两个单词 <code>word1</code> 和 <code>word2</code>，请你计算出将 <code>word1</code> 转换成 <code>word2</code><em> </em>所使用的最少操作数 。</p><p>你可以对一个单词进行如下三种操作：</p><ul>	<li>插入一个字符</li>	<li>删除一个字符</li>	<li>替换一个字符</li></ul><p> </p><p><strong>示例 1：</strong></p><pre><strong>输入：</strong>word1 = "horse", word2 = "ros"<strong><br />输出：</strong>3<strong><br />解释：</strong>horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>word1 = "intention", word2 = "execution"<strong><br />输出：</strong>5<strong><br />解释：</strong>intention -> inention (删除 't')inention -> enention (将 'i' 替换为 'e')enention -> exention (将 'n' 替换为 'x')exention -> exection (将 'n' 替换为 'c')exection -> execution (插入 'u')</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>0 <= word1.length, word2.length <= 500</code></li>	<li><code>word1</code> 和 <code>word2</code> 由小写英文字母组成</li></ul>

## template

```python
class Solution(object):
	def minDistance(self, word1, word2):
		ls_1, ls_2 = len(word1), len(word2)
		dp = list(range(ls_1 + 1))
		for j in range(1, ls_2 + 1):
			pre = dp[0]
			dp[0] = j
			for i in range(1, ls_1 + 1):
				temp = dp[i]
				if word1[i - 1] == word2[j - 1]:
					dp[i] = pre
				else:
					dp[i] = min(pre + 1, dp[i] + 1, dp[i - 1] + 1)
				pre = temp
		return dp[ls_1]
if __name__ == '__main__':
	s = Solution()
	print (s.minDistance("horse","ros"))		
	print (s.minDistance("intention","execution"))		
```

## 答案

```python

```

## 选项

### A

```python

```

### B

```python

```

### C

```python

```