# 【LeetCode】 72. Edit Distance

## Description
> Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
> You have the following 3 operations permitted on a word:
> - Insert a character
> - Delete a character
> - Replace a character

> 給予兩單字word1和word2，找出word1轉換為word2最少需要幾個運算。
> 你有三種運算可以使用：
> - 新增一個字母
> - 刪除一個字母
> - 代換一個字母

## Example:

Example 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

## Solution

* 大名鼎鼎的[萊文斯坦距離](https://zh.wikipedia.org/wiki/%E8%90%8A%E6%96%87%E6%96%AF%E5%9D%A6%E8%B7%9D%E9%9B%A2)。
* 建表、使用動態規劃(DP)。
* 設表格中x軸代表word1的子字串、y軸代表word2的子字串。對應到的格子代表最少需要的運算數。
* 表格中往下代表你需要刪除才能完成；往右代表你需要新增才能完成；往右下代表你需要代換(同時刪除和新增就是代換)。
* 該格的值為min(上、左、左上格子值)+1，如果字母一樣則不需要加一。

### Code

class Solution {
public:
    int min(int a,int b,int c)
    {
        return c>(a>b?b:a)?(a>b?b:a):c;
    }
    int minDistance(string word1, string word2) {
        int table[word1.size()+1][word2.size()+1];
        for(int i=0;i<=word1.size();i++) table[i][0]=i;
        for(int i=0;i<=word2.size();i++) table[0][i]=i;
        for (int i = 1; i <= word1.size(); i++)
	    {
		    for (int j = 1; j <= word2.size(); j++)
		    {
			    table[i][j] = min(table[i - 1][j] + 1, table[i][j - 1] + 1, table[i - 1][j - 1] + (word1[i - 1] != word2[j - 1]));
		    }
	    }
        return table[word1.size()][word2.size()];
    }
};

###### tags: `LeetCode` `C++`