题目
‘?’ 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:*p) {int m = strlen(s);int n = strlen(p);if (n==0) return m==0;<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];}};
转载请注明出处： 欢迎留言，关注
人，总是很难改正自己的缺点，
