【LeetCode】【C++】Wildcard Matching

浏览数：31 / 时间：2015年06月08日

题目

‘?’ 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

思路

此题和第十题 Regular Expression Matching极为相像，只不过这个题‘*’可代表任意字符串，而10题只能表示若干个前面字母。举例来说，此题中*可以表示a，ab，abdfefa等，也可以表示空。但10题中*不可以单独出现，其必须和它前面的字母共同构成一个表达式，比如说a*表示若干个a，也即a，aa，aaa，或空。
仍然采用DP，设置一个vectorre（n+1），存放第一个字符串截止到该位置的匹配情况，然后从第二个字符串开始遍历，遇到*要特殊处理，对于字符串2的每一位，都要从字符串1中去寻找是否可以匹配上的位置，并把相应位置标记为真。每一个位置的状态均由前一位置决定，也就是说前一位置不匹配，这一位置一定不能匹配。遍历结束后输出最后一个位置的匹配结果。

代码

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int m = strlen(s);
        int n = strlen(p);
        if (n==0) return m==0;
        if (m>30000) return false;          //没有这句话有一个case：aaaaaa居多a的过不去。。。
        vector<bool> re(m+1,false);
        re[0]=true;                         //默认第零位为匹配，因为有可能p[0]==*
        for (int i=0;i<n;i++){
            if (p[i]==‘*‘){                 //判断是否为*，*需要特殊处理
                for (int k=0;k<m;k++){
                    re[k+1]=re[k+1]||re[k]; //如果已经为真，则继续为真；否则要取决于前一位。
                }
            }
            else{
                for (int j=m;j>0;j--){      //取决于前一位，并且要求这一位匹配
                    re[j]=re[j-1]&&(p[i]==s[j-1]||p[i]==‘?‘);
                }
            }
            re[0] = re[0]&&p[i]==‘*‘;       //如果该位置不为*，则第零位不可为真
        }
        return re[m];
    }
};