厦门制作网站企业,医院网站必须建设吗,优购物官方网站女鞋,天津建设网查询分数Problem: 72. 编辑距离 文章目录 题目描述思路复杂度Code 题目描述 思路
由于易得将字符串word1向word2转换和word2向word1转换是等效的#xff0c;则我们假定统一为word1向word2转换#xff01;#xff01;#xff01; 1.确定状态#xff1a;我们假设现在有下标i#x… Problem: 72. 编辑距离 文章目录 题目描述思路复杂度Code 题目描述 思路
由于易得将字符串word1向word2转换和word2向word1转换是等效的则我们假定统一为word1向word2转换 1.确定状态我们假设现在有下标ij分别指向字符串word1和word2尾部的字符dp(i,j)表示当前的操作则 1.1. dp(i- 1, j) 1;表示删除直接把word1[i]的这个字符删除掉并前移i继续跟j对比同时操作数加一 1.2. dp(i, j - 1) 1;表示插入直接把word1[1]处的这个字符插入到word2[j]处并前移动j继续和i对比同时操作数加一 1.3. dp(i - 1, j - 1) 1;表示替换将word1[i]替换为word2[j],同时往前移动ij继续对比同时操作数加一 2.确定状态转移方程由于上述易得dp[i][j] min(dp[i - 1][j] 1;dp[i][j - 1] 1;dp[i - 1][j - 1] 1); 复杂度
时间复杂度: O ( m × n ) O(m\times n) O(m×n) 空间复杂度: O ( m × n ) O(m\times n) O(m×n) Code
class Solution {
public:/*** Dynamic programming** param word1 Given string1* param word2 Given string2* return int*/int minDistance(string word1, string word2) {int word1Len word1.length();int word2Len word2.length();vectorvectorint dp(word1Len 1, vectorint(word2Len 1));for (int i 1; i word1Len; i) {dp[i][0] i;}for (int j 1; j word2Len; j) {dp[0][j] j;}for (int i 1; i word1Len; i) {for (int j 1; j word2Len; j) {if (word1.at(i - 1) word2.at(j - 1)) {dp[i][j] dp[i - 1][j - 1];} else {dp[i][j] min3(dp[i - 1][j] 1, dp[i][j - 1] 1, dp[i - 1][j - 1] 1);}}}return dp[word1Len][word2Len];}/*** Find the maximum of the three numbers** param a Given number* param b Given number* param c Given number* return int*/int min3(int a, int b, int c) {return min(a, min(b, c));}
};
