本文主要是介绍***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 分析：
http://blog.csdn.net/linhuanmars/article/details/21198049
说一下动态规划的方法。跟Regular Expression Matching一样，还是维护一个假设我们维护一个布尔数组res[i],代表s的前i个字符和p的前j个字符是否匹配(这里因为每次i的结果只依赖于j-1的结果，所以不需要二维数组，只需要一个一维数组来保存上一行结果即可），递推公式分两种情况：
(1)p[j]不是'*'。情况比较简单，只要判断如果当前s的i和p的j上的字符一样（如果有p在j上的字符是'?'，也是相同），并且res[i]==true，则更新res[i+1]为true，否则res[i+1]=false;
(2)p[j]是'*'。因为'*'可以匹配任意字符串，所以在前面的res[i]只要有true，那么剩下的 res[i+1], res[i+2],...,res[s.length()]就都是true了。
算法的时间复杂度因为是两层循环，所以是O(m*n), 而空间复杂度只用一个一维数组，所以是O(n)，假设s的长度是n，p的长度是m。
这个作者好厉害！
爱死dp了！！一定要好好学学！！
参考代码如下：
public class Solution {public boolean isMatch(String s, String p) {if(p.length()==0)return s.length()==0;boolean[] res = new boolean[s.length()+1];res[0] = true;for(int j=0;j<p.length();j++){if(p.charAt(j)!='*'){for(int i=s.length()-1;i>=0;i--){res[i+1] = res[i]&&(p.charAt(j)=='?'||s.charAt(i)==p.charAt(j));}}else{int i = 0;while(i<=s.length() && !res[i])i++;for(;i<=s.length();i++){res[i] = true;}}res[0] = res[0]&&p.charAt(j)=='*';}return res[s.length()];}
}这篇关于***Wildcard Matching的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
