题目描述

解题思路

1. 暴力递归

这道题与剑指offer中的“正则表达式”，有相似之处。 区别在于，剑指offer中那道题好像是不处理”a”, “a*…a*”这种情况，即为主串为空，但是模式串不为空的情况，因此，加上对这种情况的特判即可。 主要是要保证，当模式串不为空时，后面的号表示前面的字符一个都不取，举例：”a” 可以与“aa*b*c*d，只要这种间隔出现的时候才可以，特判一下即可。

代码实现

class Solution { public: bool Judge(char* str1, char* str2) { //cout<<*str1<<" "<<*str2<<endl; if(*str1 == '\0' && *str2 == '\0') return true; if(*str1 != '\0' && *str2 == '\0') return false; if(*str1 == '\0' && str2 != '\0') { int flag = false; while(*str2 != '\0') { if(*str2 != '*' && *(str2+1) != '*') return false; if(*str2 == '*') flag = true; else flag = false; str2++; } return flag; } if(*(str2+1) == '*') { if(*str1 == *str2 || (*str2 == '.')) return Judge(str1, str2+2) || Judge(str1+1, str2+2) || Judge(str1+1, str2); else return Judge(str1, str2+2); } if(*str1 == *str2 || (*str2 == '.')) return Judge(str1+1, str2+1); return false; } bool isMatch(string s, string p) { char str1[550]; char str2[550]; int len1 = s.length(); int len2 = p.length(); if(len1 == 0 && len2 == 0) return true; for(int i = 0; i < len1; i++) str1[i] = s[i]; str1[len1] = '\0'; for(int i = 0; i < len2; i++) str2[i] = p[i]; str2[len2] = '\0'; return Judge(str1, str2); } };

2. 动态规划

第一种解法虽然可以过，但是效率是非常低的，因此可以用动态规划来解决，思路基于第一种的思路。 动态规划解法如下： 定义一个二维的DP数组，其中dp[i][j]表示s[0,i)和p[0,j)是否match，然后有下面三种情况 1. dp[i][j] = dp[i - 1][j - 1], if p[j - 1] != ‘*’ && (s[i - 1] == p[j - 1] || p[j - 1] == ‘.’); 2. dp[i][j] = dp[i][j - 2], if p[j - 1] == ‘*’ and dp[i][j-2] (代表模式串*前的元素未匹配;) 3. dp[i][j] = dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == ‘.’), if p[j - 1] == ‘*’ and dp[i-1][j] (代表主串中上一个元素已经被*前面的元素取代过)

代码如下

class Solution { public: bool isMatch(string s, string p) { int n = s.size(); int m = p.size(); bool dp[1010][1010]; memset(dp, false, sizeof(dp)); dp[0][0] = true; for(int i = 0; i <= n; ++i) { for(int j = 1; j <= m; ++j) { if(j > 1 && p[j-1] == '*') dp[i][j] = dp[i][j-2] || (i > 0 && (s[i-1] == p[j-2] || p[j-2] == '.') && dp[i-1][j]); else dp[i][j] = i > 0 && dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.'); } } return dp[n][m]; } };