583. 两个字符串的删除操作

72. 编辑距离

思路

动态规划，状态定义dp[i][j]为w1前i个字符转换成w2前j个字符所需要的步骤

代码

  1. /**
  2.  * @param {string} word1
  3.  * @param {string} word2
  4.  * @return {number}
  5.  */
  6. var minDistance = function(word1, word2) {
  7.   let len1 = word1.length, len2 = word2.length;
  8.   // 初始化数组
  9.   let dp = Array(len1+1).fill(0).map(item => Array(len2 + 1).fill(0))
  10.   // 初始化值， dp[i][j]表示 w1前i个字符转换成w2前j个字符所需的步骤数
  11.   for(let i = 0; i <= len1; i ++) {
  12.     dp[i][0] = i
  13.   }
  14.   for(let j = 0; j <= len2; j ++) {
  15.     dp[0][j] = j
  16.   }
  17.   for(let i = 1; i <= len1; i ++) {
  18.     for(let j = 1; j <= len2; j ++) {
  19.       // 如果相等，则当前索引位置不需要变动
  20.       if (word1[i-1] === word2[j-1]) {
  21.         dp[i][j] = dp[i-1][j-1]
  22.       } else {
  23.       // 如果不相等，则进行转换操作，步骤+1
  24.         dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
  25.       }
  26.     }
  27.   }
  28.   return dp[len1][len2]
  29. };

复杂度分析

时间复杂度 动态规划与字符串匹配 - 图1#card=math&code=O%28N%5E2%29)
空间复杂度 动态规划与字符串匹配 - 图2#card=math&code=O%28N%5E2%29)

97. 交错字符串

115. 不同的子序列

516. 最长回文子序列

132. 分割回文串 II

131. 分割回文串

139. 单词拆分

140. 单词拆分 II

514. 自由之路

10. 正则表达式匹配

44. 通配符匹配