LeetCode刷题（C++）——Edit Distance（Hard）

╰半橙微兮° 2022-06-16 06:49 277阅读 0赞

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. class Solution {
  2. public:
  3.     int minDistance(string word1, string word2) {
  4.         int m = word1.length(), n = word2.length();
  5.         vector<vector<int>> dp(m + 1, vector<int>(n + 1));
  6.         for (int i = 0; i <= m;++i) {
  7.             for (int j = 0; j <= n;++j) {
  8.                 if (i == 0) {
  9.                     dp[i][j] = j;
  10.                 }
  11.                 else if (j == 0) {
  12.                     dp[i][j] = i;
  13.                 }
  14.                 else {
  15.                     dp[i][j] = min(dp[i - 1][j - 1] + ((word1[i - 1] == word2[j - 1]) ? 0 : 1),
  16.                         min(dp[i][j - 1] + 1, dp[i - 1][j] + 1)
  17.                     );
  18.                 }
  19.             }
  20.         }
  21.         return dp[m][n];
  22.     }
  23. };

发表评论

表情：
评论列表 （有 0 条评论，277人围观）

还没有评论，来说两句吧...

相关阅读

    相关 52LeetCode刷题_LeetCode刷题手册

    虽然刷题一直饱受诟病，不过不可否认刷题确实能锻炼我们的编程能力，相信每个认真刷题的人都会有体会。现在提供在线编程评测的平台有很多，比较有名的有 hihocoder，LintCo

    女爷i女爷i/ 0 赞/ 1 阅读

    相关 LeetCode刷题指南

    以下是我个人做题过程中的一些体会：  1. LeetCode的题库越来越大，截止到目前，已经有321个问题了。对于大多数人来说，没有时间也没有必要把所有题目都做一遍（时间充

    àì夳堔傛蜴生んèńàì夳堔傛蜴生んèń/ 0 赞/ 443 阅读

    相关 Leetcode刷题

    39. 组合总和 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

    秒速五厘米秒速五厘米/ 0 赞/ 705 阅读