标签：字符 匹配 正则表达式 ne 字符串 cases 动态 规划 dp

目录

• 1. 题目
• 2. 应用
  • 2.1. Leetcode 10. 正则表达式匹配
    • 题目
    • 解题思路
    • 代码实现

1. 题目

题目列表：

序号	题目	难度
1	10. 正则表达式匹配	困难

2. 应用

2.1. Leetcode 10. 正则表达式匹配

题目

10. 正则表达式匹配

解题思路

设 \(dp[i][j]\) 表示 \(s\) 的前 \(i\) 个字符与 \(p\) 的前 \(j\) 个字符是否匹配，即子串 \(s[0 \cdots i-1]\) 与子串 \(p[0 \cdots j-1]\) 是否匹配。

显然，当两个字符串的长度都是零时，它们可以匹配成功，因此，边界条件：

\[dp[0][0] = true \]

通过分析，容易看出来：

• 如果模式串 \(p\) 的某一个位置是一个普通字符（字母或者点号）时，它只能匹配字符串 \(s\) 中的一个字符;

• 如果模式串 \(p\) 的某一个位置是一个星号字符时，它可以多次匹配 \(s\) 中的多个相同的字符。

因此，对于 \(s[0 \cdots i-1]\) 和 \(p[0 \cdots j-1]\) 的最后一个字符，有三种情况：

• 当 \(p[j-1]\) 是字母时：

  • 如果当前两个字符相等，即 \(s[i-1] = p[j-1]\)，那么，当前状态可以通过前一个状态转移得到，即

    \[dp[i][j] = dp[i-1][j-1], \ s[i-1] = p[j-1] \]

  • 如果当前两个字符不相等，即 \(s[i-1] \ne p[j-1]\)，那么，两个字符串就不匹配，即

    \[dp[i][j] = false, \ s[i-1] \ne p[j-1] \]

  因此，当 \(p[j-1]\) 是字母时，其状态转移方程为：

  \[dp[i][j] = \begin{cases} dp[i-1][j-1], &s[i-1] = p[j-1]\\ false, &s[i-1] \ne p[j-1] \end{cases} \]

• 当 \(p[j-1]\) 是 * 时，那么，它可以对字符串 \(s\) 匹配任意次：

  • 如果星号匹配零次，即星号没有匹配到字符串 \(s\) 中的字符，那么，它可以通过前一个状态转移得到

    \[dp[i][j] = dp[i][j-2], \ s[i-1] \ne p[j-2] \]

  • 如果星号匹配多次，那么，此时有两种情况：

    • 当前匹配成功，即消耗了一个字符串 \(s\) 中的字符 \(s[i - 1]\)，当前状态与前一个状态的相同；

    • 当前匹配失败，此时，需要去掉模式串 \(p\) 中的 字母 + 星号 组合。

    上述两种情况，只要有一种情况匹配成功即可。

    \[dp[i][j] = dp[i-1][j] \lor dp[i][j-2], \ s[i-1] = p[j-2] \]

    注意：这里 \(\lor\) 表示逻辑或。

  因此，当 \(p[j-1]\) 是字母时，其状态转移方程为：

  \[dp[i][j] = \begin{cases} dp[i-1][j] \lor dp[i][j-2], &s[i-1] = p[j-2]\\ dp[i][j-2], &s[i-1] \ne p[j-2] \end{cases} \]

• 当 \(p[j-1]\) 是 . 时，那么，它可以成功匹配字符串 \(s\) 中的任意字符；

  \[dp[i][j] = dp[i-1][j-1] \]

综上，状态转移方程为：

\[dp[i][j] = \begin{cases} dp[i-1][j-1], & p[j-1] \ne * ,match(s[i-1], p[j-1]) = true\\ false, & p[j-1] \ne * ,match(s[i-1], p[j-1]) = false \\ dp[i-1][j] \lor dp[i][j-2], & p[j-1] = * , match(s[i-1], p[j-2]) = true\\ dp[i][j-2], & p[j-1] = * , match(s[i-1], p[j-2]) = false \end{cases} \]

注意：长度为零的模式串不能匹配任何字符串。

代码实现

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;

        for (int i = 0; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] |= dp[i][j - 2];
                    if (match(s, i, p, j - 1)) {
                        dp[i][j] |= dp[i - 1][j];
                    }
                } else {
                    if (match(s, i, p, j)) {
                        dp[i][j] |= dp[i - 1][j - 1];
                    }
                }
            }
        }
        return dp[m][n];
    }

    private boolean match(String s, int i, String pattern, int j) {
        // 判断s[i - 1]与p[j - 1]是否匹配
        if (i == 0) {
            return false;
        }
        if (pattern.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == pattern.charAt(j - 1);
    }
}

标签：字符,匹配,正则表达式,ne,字符串,cases,动态,规划,dp
From： https://www.cnblogs.com/larry1024/p/17979801