LeetCode每日一题：wildcard matching

问题描述

> Implement wildcard pattern matching with support for'?'and'*'.
> '?' Matches any single character.
> '*' Matches any sequence of characters (including the empty sequence).
> 
> The matching should cover the entire input string (not partial).
> 
> The function prototype should be:
> bool isMatch(const char *s, const char *p)
> 
> Some examples:
> isMatch("aa","a") → false
> isMatch("aa","aa") → true
> isMatch("aaa","aa") → false
> isMatch("aa", "*") → true
> isMatch("aa", "a*") → true
> isMatch("ab", "?*") → true
> isMatch("aab", "c*a*b") → false

问题分析

‘?’只能匹配一个字符而’*’可以匹配人一个字符。这题我们可以用动态规划做。设dp[i][j]表示s的前i个字符和p的前j个字符是否匹配。三种情况：

• 若p[j-1]是‘*’，那么dp[i][j]=dp[i-1][j]||dp[i][j-1],只要s的前i-1和p的前j个或者s的前i和p的前j-1个满足即可。
• 若p[j-1]是’?’，那么dp[i][j]必须和dp[i-1][j-1]结果相同
• 若s[i]==p[j],那么dp[i][j]必须和dp[i-1][j-1]结果相同
• 其他情况： dp[i][j]=false

代码实现

public boolean isMatch(String s, String p) {
        char[] sCharArray = s.toCharArray();
        char[] pCharArray = p.toCharArray();
        boolean[][] dp = new boolean[256][256];
        int l = 0;
        if (p.length() != 0) {
            for (int i = 0; i < p.length(); i++) {
                if (pCharArray[i] != '*') l++;
            }
        }
        if (l > s.length()) return false;//p的字符数加上'?'的数目要小于s的字符数，否则根本不能匹配
        dp[0][0] = true;
        for (int i = 1; i <= p.length(); i++) {
            if (dp[0][i - 1] && pCharArray[i - 1] == '*') dp[0][i] = true;
            for (int j = 1; j <= s.length(); j++) {
                if (pCharArray[i - 1] == '*') dp[j][i] = dp[j][i - 1] || dp[j - 1][i];
                else if (pCharArray[i - 1] == '?' || pCharArray[i - 1] == sCharArray[j - 1])
                    dp[j][i] = dp[j - 1][i - 1];
                else dp[j][i] = false;
            }
        }
        return dp[s.length()][p.length()];
    }