Neovim-如何使用编辑器的神

正则表达式匹配

https://leetcode.cn/problems/regular-expression-matching/

• 首先需要注意, *是不能单独出现的, 它是和前面一个字符组成一个整体, 例如a*, 表示空字符串, 一个a, 两个a, 到任意多个a.
• 假设$f(i, j)$表示$s(1..i)$和$p(1…j)$的所有的匹配方案是否为空, 注意: 下标从1开始, 状态转移可以分为两种情况考虑:
  • 如果$p(j)$不是*, 那么$f(i, j) = f(i - 1, j - 1)\ \&\&\ (s(i) == p(j)\ ||\ p(j) == ‘.’)$
  • 如果$p(j)$是*, 那么需要根据这个*代表多少个$p(j - 1)$字符进行分类讨论:
    • 如果代表0个$p(j - 1)$, 那么$f(i, j) = f(i, j - 2)$
    • 如果代表1个$p(j - 1)$, 那么$f(i, j) = f(i - 1, j - 2)\ \&\&\ (s(i) == p(j - 1)\ ||\ p(j - 1) == ‘.’)$
    • 如果代表2个$p(j - 1)$, 那么$f(i, j) = f(i - 2, j - 2)\ \&\&\ (s(i-1) == p(j - 1)\ \&\&\ s(i) == p(j - 1)\ ||\ p(j - 1) == ‘.’)$
    • …, 最后的$f(i, j)$就是上面几种情况相与.
    • 可以发现, $f(i, j)$和$f(i - 1, j)$总是相差一个$s(i) == p(j - 1)\ ||\ p(j - 1) == ‘.’$(见下面的分析), 因此, 最终的状态转移是$f(i, j) = f(i,j-2)\ ||\ (f(i - 1, j)\ \&\&\ (s(i) == p(j - 1))\ ||\ (p(j - 1) == ‘.’))$.

状态转移优化的推导:

f[i][j] = (f[i][j - 2]) || (f[i - 1][j - 2] && (s[i] == p[j - 1] || p[j - 1] == '.')) || (f[i - 2][j - 2] && ((s[i - 1] == p[j - 1] && s[i] == p[j - 1]) || p[j - 1] == '.')) || ...

f[i - 1][j] = (f[i - 1][j - 2]) || (f[i - 2][j - 2] && (s[i - 1] == p[j - 1] || p[j - 1] == '.')) || (f[i - 3][j - 2] && ((s[i - 2] == p[j - 1] && s[i - 1] == p[j - 1]) || p[j - 1] == '.')) || ...

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size();
        int m = p.size();

        s = ' ' + s;
        p = ' ' + p;

        vector<vector<bool>> f(n + 1, vector<bool>(m + 1, false));
        f[0][0] = true;

        for (int i = 0; i <= n; i ++) {
            for (int j = 1; j <= m; j ++) {

                /* 如果p[j]不是*, 那么要求前面的s不是空 */
                if (i >= 1 && p[j] != '*') {
                        f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');
                }
                else if (p[j] == '*') {
                        /* 如果出现了*, 那么前面一定有字符, j >= 2 */
                        f[i][j] = f[i][j - 1] = f[i][j - 2] || ((i >= 1) && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.'));
                }
            }
        }

        return f[n][m];
    }
};

通配符匹配

https://leetcode.cn/problems/wildcard-matching/

状态表示和上一题一样: $f(i, j)$表示$s(1..i)$和$p(1…j)$的所有的匹配方案是否为空.

• 如果$p(j)$不是*, 那么状态转移为:

  $f(i, j) = f(i - 1, j - 1)\ \&\&\ (s(i) == p(j)\ ||\ p(j) == ‘?’)$

• 如果$p(j)$是*, 那么就需要分情况讨论:

  • 如果*表示空字符序列, 那么状态转移为:

    $f(i, j) = f(i, j - 1)$

  • 如果*表示一个字符, 那么状态转移为:

    $f(i, j) = f(i - 1, j - 1)$

  • 如果*表示两个字符, 那么状态转移为:

    $f(i, j) = f(i - 2, j - 1)$

  • ….

  总的状态转移就是上面几种情况与起来.

观察如下表达式

f[i][j] = f[i][j - 1] || f[i - 1][j - 1] || f[i - 2][j - 1] || ...
f[i - 1][j] = f[i - 1][j - 1] || f[i - 2][j - 1] || f[i - 3][j - 1] || ...

通过观察, 可以发现: $f(i, j) = f(i, j - 1) || f(i - 1, j)$, 这个优化类似于背包问题.

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        s = ' ' + s, p = ' ' + p;

        vector<vector<bool>> f(n + 1, vector<bool>(m + 1));
        f[0][0] = true;

        for (int i = 0; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (i >= 1 && p[j] != '*') {
                    f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '?');
                }
                else if (p[j] == '*') {
                    f[i][j] = (j >= 1) && f[i][j - 1] || (i >= 1) && f[i - 1][j];
                }
            }
        }

        return f[n][m];
    }
};