聖地亞歌

Leetcode P0044"Wildcard Matching" 题解

2020/08/24 Leetcode

博文中会简要介绍Leetcode P0044题目分析及解题思路。

“Wildcard Matching”是一道比较难的动态规划题，但实际上如果可以很好地理解p0010，这道题其实和p0010有异曲同工之妙。

Given an input string (s) and a pattern (p), 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).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like ? or *.

这道题使用动态规划的思想来解决。具体的递推表达式如下：

    令dp[i][j]为动态规划最优解空间，i是s中第i个字符，同理可知j是p中第j个字符，

    dp[0][0] = true; 
    显然两个空串之间互相匹配

    dp[i][0] = false, i>0; 
    显然非空s中的子串不能匹配任何空串

    dp[0][i] = dp[0][i-1], if p[i-1] == '*'; 
    其余情况皆不匹配，当p[i-1]是'*'时，可以匹配空串或者任意串，所以若它前面一个字符匹配空串，则它也可以匹配空串

    dp[i][j] = dp[i-1][j-1], if s[i-1] == p[j-1] or p[j-1] == '?'; 
    若当前字符匹配或通配，则是否匹配取决于前缀序列是否匹配

    dp[i][j] = dp[i1-1][j2] || dp[i1-1][j2-1] || dp[i1][j2-1], if p[j-1] == '*'; 
    这个情况需要重点关注。若当前p是通配符'*'，则存在三种情况，一是认为该通配符匹配任意长度的串，则看前缀字符是否和该通配符匹配；第二种是认为该通配符匹配的串从当前s中第i个开始，所以看s和p的前缀序列是否匹配；最后一种则是当前通配符匹配空串。

以下是Java的题解代码实现。

class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null && p == null)
            return true;
        
        if (s == null || p == null)
            return false;
       
        char[] sChars = s.toCharArray();
        char[] pChars = p.toCharArray();
        boolean[][] dp = new boolean[s.length()+1][p.length()+1];
        
        dp[0][0] = true;
        
        for (int i1=1; i1<=sChars.length; ++i1)
            dp[i1][0] = false;
        
        for (int i1=1; i1<=pChars.length; ++i1) {
            if (pChars[i1-1] == '*')
                dp[0][i1] = dp[0][i1-1];
        }
        
        // DP
        for (int i1=1; i1<=sChars.length; ++i1) {
            for (int j2=1; j2<=pChars.length; ++j2) {
                if (sChars[i1-1] == pChars[j2-1] || pChars[j2-1] == '?')
                    dp[i1][j2] = dp[i1-1][j2-1];
                else if (pChars[j2-1] == '*')
                    dp[i1][j2] = dp[i1-1][j2] || dp[i1-1][j2-1] || dp[i1][j2-1];
                else {
                    dp[i1][j2] = false;   
                }
            }
        }
        
        return dp[sChars.length][pChars.length];
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    bool isMatch(string s, string p) {
        vector<vector<bool>> dp(s.length()+1, vector<bool>(p.length()+1, false));
        
        dp[0][0] = true;
        
        for (int idx=1; idx<=s.length(); ++idx) {
            dp[idx][0] = false;
        }
        
        for (int idx=1; idx<=p.length(); ++idx) {
            if (p[idx-1] == '*')
                dp[0][idx] = dp[0][idx-1];
        }
        
        for (int i1=1; i1<=s.length(); ++i1) {
            for (int j2=1; j2<=p.length(); ++j2) {
                if (s[i1-1] == p[j2-1] || p[j2-1] == '?')
                    dp[i1][j2] = dp[i1-1][j2-1];
                else if (p[j2-1] == '*')
                    dp[i1][j2] = dp[i1-1][j2] || dp[i1-1][j2-1] || dp[i1][j2-1];
                else 
                    dp[i1][j2] = false;
            }
        }
        
        return dp[s.length()][p.length()];
    }
};

Search

    Table of Contents