问号和星号通配符匹配

题目描述

请实现支持’?’and’*’.的通配符模式匹配

‘?’ 可以匹配任何单个字符。
‘*’ 可以匹配任何字符序列（包括空序列）。

返回两个字符串是否匹配

函数声明为：

bool isMatch(const char *s, const char *p)

下面给出一些样例：

isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”, “*”) → true
isMatch(“aa”, “a*”) → true
isMatch(“ab”, “?*”) → true
isMatch(“aab”, “dab”) → false

示例1

输入

"ab","?*"

返回值

true

动态规划

public class Solution {
    public boolean isMatch(String s, String p) {
        //初始化
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
   		// 当p和s都为空的时候
        dp[0][0] = true;
        
        
        for (int j = 1; j <= n; j++) {
            if (dp[0][j - 1]) {
                if (p.charAt(j - 1) == '*') {
                    dp[0][j] = true;
                } else {
                    break;
                }
            }
        }
 
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 如果当前的字符匹配或者当前p的字符是？那么问题转化为子问题dp[i-1][j-1]
                if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?')
                    dp[i][j] = dp[i - 1][j - 1];
                if (p.charAt(j - 1) == '*')
                    //也可以这么写，但其实只要dp[i][j]为真，那么dp[i+1][j]一定为真，也就说dp[i][j]其实已经被dp[i+1][j]包含了
                    //dp[i + 1][j + 1] = dp[i][j] || dp[i + 1][j] || dp[i][j + 1];
                    // 如果当前匹配串的字符是*          "aa", "a*"
                    // 如果匹配第一个字符串的一个到多个字符,转移到dp[i-1][j]
                    // 如果匹配第一个字符串的0个字符,转移到dp[i][j-1]
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
}

赏

谢谢你请我吃糖果

微信