【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;
}