题解 | #牛群中的特殊编号匹配#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @param p string字符串
     * @return bool布尔型
     */
    public boolean is_match(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        // 初始化dp[0][j]
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 如果p字符串此时是.号或者 从两个字符串中取出的字符是相等的，那么就只要各自保存前一个值的状态，如果前面为true,则为true
                if (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    // 将 * 视作 0次的情况，相当于忽略前一个字符
                    dp[i][j] = dp[i][j - 2];
                    // 如果j-1=* j-2=.那么只要dp[i-1][j]为真，那么就是真
                    // 或者 j-1=* 并且 s的第i-1个字符和p的j-2个字符相等 那么同理，dp[i-1][j]为真就能匹配
                    if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
                        dp[i][j] |= dp[i - 1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
}

本题知识点分析：

1.动态规划

2.数学模拟

3.数组遍历

本题解题思路分析：

1.利用dp数组创建boolean 二维数组 行列分别代表s数组和n数组

2.初始化dp[0][j],因为如果p数组存在*的情况，那么其实可以进行初始化，*可以代表出现0次，那么0的时候的状态可以被传递给2,4，.....之类的2的倍数

3.然后根据数学模拟进行分类

4.如果p字符串此时是.号或者 从两个字符串中取出的字符是相等的，那么就只要各自保存前一个值的状态，如果前面为true,则为true

5.如果出现*号， 将 * 视作 0次的情况，相当于忽略前一个字符

6.如果j-1=* j-2=.那么只要dp[i-1][j]为真，那么就是真 或者 j-1=* 并且 s的第i-1个字符和p的j-2个字符相等 那么同理，dp[i-1][j]为真就能匹配

本题使用编程语言: Java

如果你觉得本题对你有帮助的话，可以点个赞支持一下，感谢~