題目： 編輯距離
給你兩個單詞 word1 和 word2，請你計算出將 word1 轉換成 word2 所使用的最少運算元 ，
你可以對一個單詞進行如下三種操作：
插入一個字符
洗掉一個字符
替換一個字符
示例 1：
輸入：word1 = "horse", word2 = "ros"
輸出：3
解釋：
horse -> rorse (將 'h' 替換為 'r')
rorse -> rose (洗掉 'r')
rose -> ros (洗掉 'e')
示例 2：
輸入：word1 = "intention", word2 = "execution"
輸出：5
解釋：
intention -> inention (洗掉 't')
inention -> enention (將 'i' 替換為 'e')
enention -> exention (將 'n' 替換為 'x')
exention -> exection (將 'n' 替換為 'c')
exection -> execution (插入 'u')
思路：
定義一個陣列 pd[i][j] 表示將 word1 前 i 個 字母替換為 word2 前 j 個字母所用的最少修改次數
若兩個單詞的字母相等： 則 dp[ i ][ j ] = dp[ i - 1 ][ j - 1 ];
否則在三個操作之間去一個最小的：dp[ i ][ j ] = min( min( dp[ i - 1 ][ j ], dp[ i ][ j - 1 ] ), dp[ i - 1 ][ j - 1 ] );
class Solution { public: int minDistance(string word1, string word2) { int len1 = word1.size(); int len2 = word2.size(); int dp[len1+1][len2+1]; memset(dp,0,sizeof(dp)); for( int i = 0; i <= len1; i++ ) dp[i][0] = i; for( int j = 0; j <= len2; j++ ) dp[0][j] = j; for( int i = 1; i <= len1; i++ ) { for( int j = 1; j <= len2; j++ ) { if( word1[ i - 1 ] == word2[ j - 1 ] ) { dp[i][j] = dp[i-1][j-1]; } else { dp[i][j] = min( dp[i-1][j-1], min( dp[i-1][j], dp[i][j-1] ) ) + 1; } } } return dp[len1][len2]; } };
2020-04-06-15:00:52
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/42998.html
標籤：C++
上一篇：STL之vector
下一篇：C++中不引人矚目的細節