算法学习之动态规划(leetcode 44 Wildcard Matching）

leetcode 44. 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
           

解题思路，首先先弄明白?和*在其中的含义，

- ?代表一个的意思
     - *代表个或者多个的意思
           

然后自己考虑的时候，需要使用到动态规划的想法，就是构建一个2D表格，进行一个递推过程。首先，明确定义，定义二维布尔矩阵dp[m][n]，第一个坐标为待匹配的字符串，第二个坐标为模式串，dp[x][y]的含义是字符串前x个字符与模式串前y个字符是否匹配，若匹配则为true，否则为false.

递推核心过程如下，

如果当前需要判断dp[i+1][j+1]，即字符串的下标到达i，模式串的下标到达j。此时，分为两种情况

p.charAt(j) == '?' || s.charAt(i) == p.charAt(j)。
    含义是如果p为此处字符为?或者p此处的字符与s此处的字符相同，
    则显然dp[i+][j+] = dp[i][j]
  p.charAt(j) == '*'。这种情况较为复杂。分情况讨论。
     A. *代表个字符，则此时dp[i+][j+]=dp[i+][j]
     B. *代表个字符，则此时dp[i+][j+]=dp[i][j]
     C. *代表个字符，则此时dp[i+][j+]=dp[i-][j]
     D. *代表个字符，则此时dp[i+][j+]=dp[i-][j]
     ...
     因此，最后的统一结果为
     dp[i+][j+]=dp[i+][j] || dp[i][j] || dp[i-][j] || 
                  dp[i-][j] || ... || dp[][j]
     需要注意的是按照上述公式，可以得到
     dp[i][j+] = dp[i][j] || dp[i-][j] || dp[i-][j] ||  
                  dp[i-][j] || ... || dp[][j]
     因此dp[i+][j+] = dp[i+][j] || dp[i][j+]   
  s.charAt(i) != p.charAt(j) 不匹配
     dp[i+][j+] = false;
           

需要注意的细节为

1 需要二维布尔矩阵开始全部初始化为false，然后将dp[0][0]=true，将第0行进行初始化，dp[0][j+1] = dp[0][j] && (p.charAt(j) == ‘*’)，此句话的意思是如果前面匹配，当前为 *，则肯定匹配。

2 先统计下p中非*的有多少，如果比s的总字符长度还大，说明没有必要继续做下去了（不可能匹配成功）。

具体的代码实现

public class Solution {
    public boolean isMatch(String s, String p) {
        if(s == null || p == null) return true;

        int sLen = s.length();
        int pLen = p.length();

        //非star数目统计
        int countNotStar = ;
        for(int i = ; i < pLen; i++){
            if(p.charAt(i) != '*'){
                countNotStar += ;
            }
        }
        //如果非star数目比s长度还大，不可能匹配
        if(countNotStar > sLen) return false;

        //初始化二维矩阵，全为false
        boolean[][] dp = new boolean[sLen+][pLen+];
        dp[][] = true;

        for(int j = ; j < pLen; j++){
            //初始化第一行数据
            dp[][j+] = dp[][j] && (p.charAt(j) == '*');

            for(int i = ; i < sLen; i++){
                //情况1
                if(p.charAt(j) == '?' || p.charAt(j) == s.charAt(i)){
                    dp[i+][j+] = dp[i][j];
                }
                //情况2
                else if(p.charAt(j) == '*'){
                    dp[i+][j+] = (dp[i][j+] || dp[i+][j]);
                }
                //not match
                else{
                    dp[i+][j+] = false;
                }
            }
        }

        return dp[sLen][pLen];
    }
}