题目:正则匹配,不过pattern串中只有小写字母,和'.'外加'*'。
其实这道题目如果没有'*'直接一路匹配过去就好了,不用想太多;但是题目中有这个,就得想办法解决了。'*'在正则中表示匹配0个或多个前一个字符,这样的话,如果当前是'*'就得知道前一个字符,这就引导我们去做从后向前的字符串匹配了,具体代码如下:
点击(此处)折叠或打开
- bool isMatch(string s, string p){
- int s_len=s.length(), p_len=p.length();
- // dp[i][j] 表示s[i:], p[j:]能否完全匹配
- vector<vector<bool> > dp(s_len+1, vector<bool>(p_len+1, false));
- dp[s_len][p_len]=true;// 空匹配为真
- // pattern 串有可能匹配空,所以
- for(int i=s_len; i>=0; i--){
- for(int j=p_len-1; j>=0; j--){
- // 先判断当前是否能够匹配
- bool is_match = i<s_len&&(s[i]==p[j]||p[j]=='.');
- if(j+1<p_len && p[j+1]=='*'){
- // 匹配0个或者多个(多个的时候用到了“后向迭代思路”)
- dp[i][j]=dp[i][j+2]||(is_match && dp[i+1][j]);
- }else{
- dp[i][j]=is_match && dp[i+1][j+1];
- }
- }
- }
- return dp[0][0];
- }