leetocde10.正则表达式
题目：请实现一个函数用来匹配包含’.‘和’*‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"及"ab*a"均不匹配。
因为 * 的存在让整个题目复杂，那我们把下一个字符是不是 * 作为划分依据。
Case 1. 当模式中的第二个字符不是“*”时： 1、如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。 2、如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。 Case 2 . 当模式中的第二个字符是“*”时： 可以有3种匹配方式：
1、模式后移2字符，相当于x*被忽略；比如 str : ab , pattern : b*ab 2、字符串后移1字符，模式后移2字符，x*相当于只匹配一个字符；ab 和 a*b 3、字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位；aab 和a*b
bool isMatch(string s, string p) { if (p.empty()){ return s.empty(); } const char* str = s.c_str(), *pat = p.c_str(); return isMatchCore(str, pat); } bool isMatchCore(const char *s, const char *p) { if ((*p) == '\0') { return *s == '\0'; } if (*(p + 1) == '*') { if (*p == *s || (*p == '.' && *s != '\0')) { return isMatchCore(s + 1, p) || isMatchCore(s + 1, p + 2) || isMatchCore(s, p + 2); } else { return isMatchCore(s, p + 2); } } else if (*p == *s || (*p == '.' && *s != '\0')){ return isMatchCore(s + 1, p + 1); } else { return false; } }方法类似于44题 但是转移方程不同
note1： * 跟着他前一个字符走，前一个能匹配上 s[i-1]，* 才能有用，前一个都不能匹配上 s[i-1]，* 也无能为力，只能让前一个字符消失，也就是匹配 0 次前一个字符: dp[i][j] = dp[i][j - 2]; 如： s:ab p:ac*b i=2 j=3 把c*当作整体忽略了
note2: * 前一个字符可以匹配上s[i-1] dp[i][j] = dp[i-1][j] // 多个字符匹配的情况 or dp[i][j-1] // 单个字符匹配的情况 or dp[i][j-2] // 没有匹配的情况
public boolean isMatch(String s, String p) { // s = "a"; p = "*"; s = "$" + s; // s和p前面加冗余字符的作用 见下面解释 p = "$" + p; int lens = s.length(), lenp = p.length(); boolean[][] dp = new boolean[lens+1][lenp+1]; dp[0][0] = true; for (int i = 1; i <= lens; ++i) { char cs = s.charAt(i - 1); for (int j = 1; j <= lenp; ++j) { char cp = p.charAt(j - 1); if (cs == cp || cp == '.') // 直接匹配上 dp[i][j] = dp[i - 1][j - 1]; else if (cp == '*') { // 没有直接匹配上 而且遇到 * if (cs != p.charAt(j - 2) && p.charAt(j - 2) != '.') // note1 dp[i][j] = dp[i][j - 2]; // 匹配0个(空串) else // note2 dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j]; } } } return dp[lens][lenp]; } s = "$" + s; p = "$" + p;s和p前面加冗余字符 $ 的作用 主要有两个:
不用像44题前面那样初始化dp[0][j] 也就是当s是空串时，和p的前j的字符匹配情况，因为s非空在遇到*时else if (cp == ‘*’)后面: 会取到j-2的索引值 索引j从1开始，如果s和p的第一个字符天然匹配之后，就不会执行else if 后面的内容， 也就取不到j-2了。下一次进入循环j=2 j-2开始有效了。注意的是：前面加的冗余字符不能是s和p里出现的字符 比如加上a: 如果s: a, p: * 会判错。
