【LeetCode】动态规划——72.编辑距离、10.正则表达式匹配

LeetCode题目链接
https://leetcode.cn/problems/edit-distance/description/
https://leetcode.cn/problems/regular-expression-matching/description/

题解
72.编辑距离
本题要定义为长度为i、长度为j的字符串的最少编辑次数，每次判断字符的下标为i-1、j-1。dp[i][j]的状态由dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]共同决定，从dp[i-1][j]到dp[i][j]表示word1加上下标为i-1的字符后，与word2的距离差距，可以得知dp[i][j]=dp[i-1][j]+1；同理可得dp[i][j]=dp[i][j-1]+1，即word1加上第j-1个字符后所需的操作的个数多了个1，可以理解为删除；同理，此处需判断两个字符串的当前下标为i-1的字符和下标为j-1的字符是否相等，如果相等，就不需要增加操作个数，直接等于dp[i-1][j-1]即可，如果不相等，需要替换一次（不是删除两次，要求最小操作个数），则就等于dp[i-1][j-1]+1。由此可以的值最终dp[i][j]由上三者取最小值即可。同时对于初始化，由于第0行和第0列分别代表空字符串与word1、word1的挨个字符所需的操作次数，因此需要初始化为对应的递增值，简单点可以直接初始化为下标i、下标j的值即可。

10.正则表达式匹配
思路详见题解，c++版代码详见评论区。
需要注意的是判断*这个字符时，它与前面一个字符的组合可以被干掉，也就是可以重复0次（根据题意），因此可以往前跳两位字符再继续判断。

代码

#include <iostream>
#include <string>
#include <vector>
using namespace std;class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word2.size() + 1, vector<int>(word1.size() + 1, 0));for (int i = 0;i <= word2.size();i++) {dp[i][0] = i;}for (int j = 0;j <= word1.size();j++) {dp[0][j] = j;}for (int i = 1;i <= word2.size();i++) {for (int j = 1;j <= word1.size();j++) {if (word2[i - 1] == word1[j - 1]) {dp[i][j] = min(dp[i - 1][j] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j - 1]));}else {dp[i][j] = min(dp[i - 1][j] + 1, min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1));}}}printf("dp[i][j]\n");for (int i = 0;i <= word2.size();i++) {for (int j = 0;j <= word1.size();j++) {printf("%d ", dp[i][j]);}printf("\n");}return dp[word2.size()][word1.size()];}
};int main() {Solution s;string word1 = "intention";string word2 = "execution";printf("%d", s.minDistance(word1, word2));return 0;
}

//10.正则表达式匹配
#include <iostream>
#include <vector>
#include <string>
using namespace std;class Solution {
public:bool isMatch(string s, string p) {if (p.empty() && !s.empty()) return false;//if (s.empty() && !p.empty() && p[j - 1] != '*') return false;vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1, false));dp[0][0] = true; //两个空字符串for (int j = 1;j <= p.size();j++) {  //s为空，但p因为* 可以干掉一个字符（即题意中的可以重复零次）if (p[j] == '*')dp[0][j + 1] = dp[0][j - 1];}for (int i = 1;i <= s.size();i++) {for (int j = 1;j <= p.size();j++) {if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {dp[i][j] = dp[i - 1][j - 1];}else {if (p[j - 1] == '*') {if (s[i - 1] == p[j - 2] || p[j - 2] == '.') {dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j];   //重复0次、重复1次、重复2次以上}else {dp[i][j] = dp[i][j - 2];  //不匹配，*干掉一个字符}}}}}return dp[s.size()][p.size()];}
};int main() {Solution s;string str1 = "ab";string str2 = ".*";printf("%d", s.isMatch(str1, str2));return 0;
}