Given an input string (s) and a pattern ℗, implement regular expression matching with support for ‘.’ and ‘*’.

‘?’ Matches any single character. (?匹配任何单个字符)
‘*’ Matches any sequence of characters (including the empty sequence). (\*匹配任何字符串,包括空串,也就是说如果s=bb, p= \*bb, 也是匹配的)

The matching should cover the entire input string (not partial).

Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

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


这道题,匹配方式是,在 s 中一个字符一个字符得查看,同时也在模式 p 中查看,但是在查看两个字符串的时候,查询坐标是不一样的。我们假设dp[x][y] 表示s[0…x-1]与p[0…y-1]的匹配与否(true,false),也就是s中前x个字符与p中前y个字符。可以采用动态规划的算法,来计算下一对字符的情况。假设我们已经匹配过dp[i][j],下一个是计算dp[i+1][j+1],根据p[j] (p[j]表示字符串p中下标为j的字符)的值,因此有三种情况

1. p[j]为"?"或者p[j] = s[i](含义是如果p为此处字符为?或者p此处的字符与s此处的字符相同,)
    则dp[i+1][j+1] = dp[i][j]

2. 如果p[j]为"*",A) *可以继续0个字符,所以s串继续查找下一个字符s[i+1],匹配串p保持不动,B) 或者*匹配当前的字符。
    则dp[i+1][j+1] = dp[i][j+1] || dp[i+1][j] 
   这个推倒我们可以一步一步来。
   (1.) 假如*匹配0个字符,则dp[i+1][j+1]=dp[i+1][j](子串s[0..i]与子串p[0..j]的匹配情况与s[0..i]与p[0..j-1]的匹配情况一致);
   
   (2.) 假如*匹配1个字符,则dp[i+1][j+1]=dp[i][j](子串s[0..i]与子串p[0..j]的匹配情况与s[0..i-1]与p[0..j-1]的匹配情况一致);
   
   (3.) 假如*匹配k个字符(从i位置往左),则dp[i+1][j+1]=dp[i-k][j](子串s[0..i]与子串p[0..j]的匹配情况与s[0..i-1-k]与p[0..j-1]的匹配情况一致);
    =》dp[i+1][j+1] = dp[i+1][j] || 
                    dp[i][j] || 
                    dp[i-1][j] || 
                    dp[i-2][j] ||  
                    dp[i-3][j] || ... || 
                    dp[0][j]
3.s[i] != p[j] 不等
     则dp[i+1][j+1] = false;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
bool isMatch(string s, string p) {
int ssz = s.size();
int psz = p.size();
vector<vector<bool> > dp(ssz+1, vector<bool>(psz+1, false)); //二维数组
dp[0][0] = true;

int numstar = 0;
for(int i = 0;i < psz; i++){
if(p[i] != '*'){
numstar +=1;
}
}
if(numstar > ssz) return false;

for(int j = 0; j < psz; j++){
if(p[j] == '*'){
dp[0][j+1] = dp[0][j]; // 第一行初始化
}
for(int i = 0; i < ssz; i++){
// 情况1
if(p[j] == '?' || p[j] == s[i])
dp[i+1][j+1] = dp[i][j];
// 情况2
else if (p[j] == '*')
dp[i+1][j+1] = dp[i][j+1] || dp[i+1][j];
else
dp[i+1][j+1] = false;
}
}
return dp[ssz][psz];
}
};

https://blog.csdn.net/maxiaotiaoti/article/details/52965116

https://blog.csdn.net/monkey_rose/article/details/79053773