Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character
编辑距离是算法导论的一道作业题，不过leetcode的这道题比较简单，权重都一样。
令dp[i][j]代表word1[0..i]和word2[0..j]的编辑距离
则当word1[i]==word[j]时，dp[i][j]=dp[i-1][j-1]
word1[i]!=word[j]时，dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
class Solution {
public:
inline bool find(const string &str,char &ch)
{
for(char c:str)
{
if(c==ch)
return true;
}
return false;
}
inline int min(int a,int b,int c)
{
if(a<=b &&a<=c)
return a;
if(b<=a &&b<=c)
return b;
else return c;
}
int minDistance(string word1, string word2) {
int row = word1.length();
int col = word2.length();
if(row== || col==) return row+col;
vector<vector<int>> dp(row,vector<int>(col,));//dp[i][j]代表word1[0..i]和word2[0..j]的编辑距离
//先确定第一行和第一列
for(int i=;i<col;i++)
{
if(find(word2.substr(,i+),word1[]))
dp[][i] = i;
else
dp[][i] = i+;
}
for(int i=;i<row;i++)
{
if(find(word1.substr(,i+),word2[]))
dp[i][] = i;
else
dp[i][] = i+;
}
for(int i=;i<row;i++)
{
for(int j=;j<col;j++)
{
if(word1[i] == word2[j])
dp[i][j] = dp[i-][j-];
else
dp[i][j] = min(dp[i-][j],dp[i][j-],dp[i-][j-])+;
}
}
return dp[row-][col-];
}
};