使用动态规划求解字符串问题

2018-01-09 10:18:28来源:网络收集作者:咖啡不加糖人点击

分享

阿里云爆款72. Edit
Distance--字符串编辑问题
问题描述:
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


问题解析:

1. 本题是求两个字符串s1和s2,编辑s1让其变为s2。可以在s1中插入字符操作、删除字符操作、替换字符操作,每次操作增加步骤1次,求s1变为s2的最小步骤数。
2. 解决此类问题经典解法就是用动态规划。
       (1)s1大小为size1,s2大小为size2。定义一个size1+1*size2+1的dp,其中dp[i][j]表示s1的前i的字符变为和s2的前j个字符所需要的最小步骤数。
       (2)dp[i][j]的值应该是:当s1[i]==s2[j]时,dp[i][j]==dp[i-1][j-1];当s[i] != s[j]时,dp[i][j] = dp[i-1][j]+1(删除一个字符)、dp[i][j] = dp[i][j-1] + 1(添加一个字符)、dp[i][j] = dp[i-1][j-1] + 1(替换一个字符)。选择三者步骤数最少的一个。


代码如下:
class Solution {
public:
// 使用动态规划来解决此问题,创建dp,dp[i][j]表示word1的i个字符转化为word2的前j个字符所需要的花费
int minDistance(string word1, string word2)
{
int m = (int)word1.size();
int n = (int)word2.size(); // 创建dp
vector>dp(m+1, vector(n+1, 0));
// 初始化第一行,代表word1为空时转化为word2
for(int j=1; j<=n; ++j)
dp[0][j] = dp[0][j-1] + 1;
// 初始化第一列,代表word2为空时转化为word1
for(int i=1; i<=m; ++i)
dp[i][0] = dp[i-1][0] + 1;
for(int i=1; i<=m; ++i)
{
for(int j=1; j<=n; ++j)
{
// dp[i-1][j]表示word1前i-1转换为word2前j个,需要花费,删掉1个就是前i和前j
// dp[i][j-1]表示word1前i转换为word2前j-1个,需要花费,添加1个就是前i和前j
// dp[i-1][j-1]表示word1前i-1转换为word2前j-1个需要花费。word1[i]==word2[j],则不需要花费就是前i和前j.否则需要替换多花费1
int z;
dp[i][j] = dp[i-1][j] < dp[i][j-1] ? dp[i-1][j]+1 : dp[i][j-1]+1;
z = (word1[i-1] == word2[j-1] ? dp[i-1][j-1] : dp[i-1][j-1]+1);
dp[i][j] = dp[i][j] < z ? dp[i][j] : z;
}
}
return dp[m][n];
}
};

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台