实现正则表达式匹配、动态规划
题目描述
请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配
解法
要判断当前pattern字符和str当前字符是否匹配，要看他们之前字符的状态
定义一个动态数组dp[str.size() 1][pattern.size() 1]，全初始化为0，假如str当前位置i，pattern当前位置j
情况1：pattern[j-1]!=’‘，即前一个字符不为’‘
代码语言：javascript复制1：pattern[j-1]=='.'，即匹配串前一个字符为'.'，因为'.'可以匹配一个字符，所以dp[i][j]=dp[i-1][j-1]
2: pattern[j-1]==str[i-1]，即前一个字符是相同的，也是匹配一个字符，dp[i][j]=dp[i-1][j-1]
3： pattern[j-1]！=str[i-1]，即前一个字符是不匹配的，那dp[i-1][j-1]肯定是0，dp[i][j]也肯定是0，这个情况不用管情况2： pattern[j-1]==’‘，即前一个字符为’‘，然后以下两种可能的情况，只要有一种成立即可
代码语言：javascript复制1：匹配0个字符：dp[i][j]=dp[i][j-2]
2: 匹配1或多个个字符：dp[i][j]=dp[i-1][j]初始化dp数组：考虑当pattern在位置0时，如果str不在位置0则匹配失败，如果str在位置0则匹配成功
考虑越界情况，保证下标不会越界
代码语言：javascript复制class Solution {
public:
bool match(char* s, char* p)
{
int sn = strlen(s), pn = strlen(p);
vector<vector<char>> dp(sn 1, vector<char>(pn 1, 0));
for (int i=0; i<=sn; i) {
for (int j=0; j<=pn; j) {
// 初始条件
if (j == 0) dp[i][j] = (i == 0);
else {
// 如果没有 '*'
if (p[j-1] != '*') {
if (i >= 1 && j>=1 && (s[i-1] == p[j-1] || p[j-1] == '.')) {
dp[i][j] = dp[i-1][j-1];
}
}
// 如果有 '*'
else {
// 重复 0 次
if (j >= 2) {
dp[i][j] |= dp[i][j-2];
}
// 重复 1 次或者多次
// 这里要用 | 连接， 不然重复 0 次的会直接覆盖
if (i >= 1 && j>=2 && (s[i-1] == p[j-2] || p[j-2] == '.')) {
dp[i][j] |= dp[i-1][j];
}
}
}
}
}
return dp[sn][pn];
}
};
