[72] Edit Distance

感覺是一個經典的題目。我怎麼會沒寫過呢？XD

問。最少步數將word 1 改成word 2。可以新增，刪除和取代。

用matrix 去代表word 1 和 word2，分別在矩陣的左邊跟上面先 生出一排的初始值，

matrix[0][0] 就表是word1 和word2 都是空的情況。 多生出了初始值很容易忘記在比對

word1 [i] 跟 word2[j] 的時候，忘記把index 減一。

除此之外，就是一行一行往下填了。如果該欄位的 字元相同，表示它的步數和 各自前一個一樣。直接取matrix的左上角的步數填下來就可以了。（這個圖解就去找leetcode上的影片看吧XD）

若是不同，那麼它需要找(1)左邊(2)上面(3)左上的最小值再加一步，來達成目標。

（代表新增，刪除和取代）

最後回傳matrix 的最右下角！就是將word1 改成word2 會需要的最少步數了

int minDistance(char* word1, char* word2) {

int l1 = strlen (word1);

int l2 = strlen (word2);

if (l1 ==0)

return l2;

if (l2==0)

return l1;

int **matrix = calloc ((l2+1),sizeof(int*));

for (int i=0; i<l2+1;i++)

matrix[i]=calloc (l1+1, sizeof(int));

for (int i=0;i<l2+1; i++)

for (int j=0;j<l1+1; j++)

{

if (i==0)

matrix[i][j]=j;

else if (j==0)

matrix[i][j]=i;

else if (word1[j-1]== word2[i-1])

matrix[i][j]= matrix[i-1][j-1];

else

{

int left = matrix[i][j-1];

int up = matrix[i-1][j];

int l_up= matrix[i-1][j-1];

if (left <=up && left <= l_up)

matrix[i][j]= left +1;

else if (up <= left && up <= l_up)

matrix[i][j]= up +1;

else if (l_up <= left && l_up <= up)

matrix[i][j]= l_up +1;

}

}

int ret = matrix[l2][l1];

for (int i=0; i<l2+1;i++)

free(matrix[i]);

free(matrix);

return ret;

}