10. 正则表达式匹配

如果p[j+1] 不是通配符 ‘’ ，则f[i] [j]是真，当且仅当s[i]可以和p[j]匹配，且f[i+1] [j+1]是真；
如果p[j+1]是通配符 '’，则下面的情况只要有一种满足，f[i] [j]就是真；
f[i] [j+2]是真；
s[i]可以和p[j]匹配，且f[i+1] [j]是真;

class Solution {
public:
    vector<vector<int>> dp;
    int lens, lenp;
    bool isMatch(string s, string p) {
        lens = s.size();
        lenp = p.size();
        dp = vector<vector<int>>(lens + 1, vector<int>(lenp + 1, -1));
        return sol(s, p, 0, 0);
    }
    
    bool sol(string &s, string &p, int x, int y) {
        if(dp[x][y] != -1) return dp[x][y];
        if(y == lenp) return dp[x][y] = x == lens;
        bool match = (s[x] == p[y] || p[y] == '.') && x < lens;// 越界
        bool tmp;
        if(p[y + 1] == '*' && y + 1 < lenp) {
            tmp = ( (match && sol(s, p, x + 1, y) ) || sol(s, p, x, y + 2));// 多匹配||0匹配
        } else {
            tmp = match && sol(s, p, x + 1, y + 1);
        }
        return tmp;
    }
};

72. 编辑距离

状态表示：f[i,j] 表示将 word1 的前 i 个字符变成 word2 的前 j 个字符，最少需要进行多少次操作。
状态转移，一共有四种情况：

  • 将 word1[i]删除或在 word2[j]后面添加 word1[i]，则其操作次数等于 f[i−1,j]+1;
  • 将 word2[j]删除或在 word1[i]后面添加 word2[j]，则其操作次数等于 f[i,j−1]+1;
  • 如果 word1[i]=word2[j]，则其操作次数等于 f[i−1,j−1];
  • 如果 word1[i]≠word2[j]，则其操作次数等于 f[i−1,j−1]+1；
    时间复杂度分析：状态数 O(n2)，状态转移复杂度是 O(1)，所以总时间复杂度是 O(n2); 
class Solution {
public:
    vector<vector<int>> dp;
    int len1, len2;
    int minDistance(string word1, string word2) {
        len1 = word1.size(), len2 = word2.size();
        dp = vector<vector<int>>(len1 + 1, vector<int>(len2 + 1));
        for(int i = 0; i <= len1; i ++) dp[i][0] = i;
        for(int i = 0; i <= len2; i ++) dp[0][i] = i;

        for(int i = 1; i <= len1; i ++) {
            for(int j = 1; j <= len2; j ++) {
                if(word1[i - 1] != word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = dp[i - 1][j - 1];
                }

                dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j]);
                dp[i][j] = min(dp[i][j - 1] + 1, dp[i][j]);

            }
        }
        return dp[len1][len2];
    }
};

大概率 持续更新。。。。。。。。 待续