Leetcode 72 編輯距離

題目描述：

給出word1和word2兩個詞，找出將word1轉化為word2所需要的最小步驟。

對一個詞所允許的三種操作如下：

a) 插入一個字元

b) 刪除一個字元

c) 替換一個字元

背景：

當拼寫檢查器遇到了一個可能的拼寫錯誤，它從詞典中尋找最接近的其它正確詞。如何衡量"最接近"？

一個自然的衡量方法是兩個詞的匹配度，即從一個詞轉變到另外一個詞所需的步驟。

例如：

從b e r t

到b e t t y

需要兩步操作：

1.替換r為t，得到 bett

2.尾部插入y，得到 betty

思路：

假設兩個詞的距離為n，那麼每個詞尾部任意插入一個字元後，距離是多少呢？

例如，bert和betty的距離為2，如果尾部同時插入相同的字元，顯然，距離還是2；

如果插入不同的字元，距離就應該等於3嗎？

不一定。

例如bert和betty尾部分別插入y和z，得到：

b e r t y

b e t t y z

只需要對第一個詞做兩步操作：替換r為t，並在尾部插入z，就可轉換為相同的詞，

所以距離仍然是2。

因此如果尾部的兩個字元不同，應該計算如下三種距離並求最小值：

1. 將詞1和詞2同時去掉尾部字元，計算得到的新詞之間的距離，再加1；

2.將詞1的尾部去除，計算它和詞2的距離，再加1(因為第一步是去除詞1尾部字元)；

3.將詞2的尾部去除，計算它和詞1的距離，再加1(因為第一步是去除詞2尾部字元).

程序清單如下：

class Solution {npublic:n int minDistance(const string& s1, const string& s2) {n g_dist.clear();n g_dist.resize(s1.size());n for (auto& v : g_dist)n v.assign(s2.size(), -1);nn return _EditDistance(s1, s2, s1.size(), s2.size());n }nprivate:n intn _EditDistance(const std::string& s1, const std::string& s2, size_t s1len, size_t s2len)n {n if (s1len == 0)n return s2len;nn if (s2len == 0)n return s1len;nn if (g_dist[s1len - 1][s2len - 1] != -1)n return g_dist[s1len - 1][s2len - 1];nn int dist1 = std::numeric_limits<int>::max(),n dist2 = std::numeric_limits<int>::max();n if (s1[s1len - 1] == s2[s2len - 1])n dist1 = _EditDistance(s1, s2, s1len - 1, s2len - 1);n elsen {n dist2 = std::min<int>(1 + _EditDistance(s1, s2, s1len - 1, s2len),n 1 + _EditDistance(s1, s2, s1len, s2len - 1));n dist2 = std::min<int>(dist2,n 1 + _EditDistance(s1, s2, s1len - 1, s2len - 1));n }nn const int res = std::min(dist1, dist2);n g_dist[s1len - 1][s2len - 1] = res;n return res;n }nn std::vector<std::vector<int> > g_dist;n};n

耗時6ms，擊敗97.61%的用戶。