44 通配符匹配.md

44 通配符匹配（双指针先放下）

题目：

给定一个字符串s和一个字符串模式p，实现一个支持?和*的通配符匹配。

解题（动态规划）：

什么是动态规划？

• 一个问题可以分解成许多子问题
• 存在一种结构，可以从子问题推导出父问题
• 动态规划是从最开始的子问题，逐渐推算出要求解的问题。

这道题创建了一个匹配矩阵，模式串p[:j]能否匹配字符串s[:i]。需要注意的是这里的i和j都是标记第一个字符为1，所以，当前字符串为s.charAt(i)。

public static boolean isMatch2(String s, String p) {
        int m = s.length(), n = p.length();
        
        //创建了(m+1)*(n+1)的矩阵
        boolean[][] f = new boolean[m + 1][n + 1];
        
        //双方都是空字符串，当然匹配
        f[0][0] = true;
        
        //当字符串s为null，模式串p在什么情况下匹配？（上一个能匹配，这次是*，肯定也能匹配）
        for(int i = 1; i <= n; i++){
            f[0][i] = f[0][i - 1] && p.charAt(i - 1) == '*';
        }
        
        //p.charAt(i-1)是指当前字符串，i是从1-n的某个值
        
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
            	
            	//A：如果当前的两个字符相匹配，则同时向前退一步，看能不能匹配
            	//B：如果模式串当前的字符为?，这表示能匹配任何字符串的当前字符，匹配结果就看同时向前一步的结果了
                if(s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?'){
                    f[i][j] = f[i - 1][j - 1];
                }
                
                //A：如果模式串的*表示空，则需要看看，模式串上次的结果与字符串的匹配情况，例如ab,ab*
                //B：如果*不表示空，那么需要看字符串前面的一个结果，是否与模式串匹配，例如abcd,ab*
                if(p.charAt(j - 1) == '*'){
                    f[i][j] = f[i][j - 1] || f[i - 1][j];
                }
            }
        }
        return f[m][n];
    }