https://leetcode.com/problems/regular-expression-matching/
给一个原串s和一个模式串p，求模式串能不能完全匹配原串
模式串中含有‘.‘和‘*‘，‘.‘可以匹配任意字符，‘*‘需要和它前面的字符结合起来，表示0个或任意多个该字符
记忆化搜索：
这道题的难点就在于‘*‘，如果没有‘*‘，那么很简单的逐个匹配就可以了。现在有了‘*‘，我们需要对它讨论两种情况，使用0次还是使用多次
我使用了递归的深搜算法，在过程中存储结果实现记忆化优化
递归函数f(i,j)有两个参数，表示原串从下标i开始与模式串从下标j开始是否匹配
首先我们看p[j+1]是否为‘*‘，如果是的话，分情况讨论
我们使用0次p[j]，那么就相当于‘*‘和其前面的字符不存在，f(i,j) = f(i,j+2)
我们使用多次p[j]，那么前提是s[i]==p[j]，然后我们匹配s中的一个字符并保持p不变，这样就可以实现任意数量的匹配了，于是f(i,j) = f(i+1,j)
如果p[j+1]不为‘*‘，那么就单独匹配s[i]和p[j]即可，然后f(i,j) = f(i+1,j+1)
在递归过程中，对于每个(i,j)得到的结果，我会存储下来，如果之后再次递归到该状态，就可以免去重复计算，直接取值
1 class Solution { 2 public: 3 int* UsedPairs; 4 int slen, plen; 5 6 int PairToInt(int i, int j) { 7 return i * (plen + 1) + j; 8 } 9 10 bool match(string& s, string& p, int i, int j) { 11 if (j == plen) return i == slen; 12 if (UsedPairs[PairToInt(i, j)] >= 0) return UsedPairs[PairToInt(i, j)]; 13 14 bool FirstMatch = i < slen && (s[i] == p[j] || p[j] == ‘.‘); 15 bool Result; 16 if (j + 1 < plen && p[j + 1] == ‘*‘) { 17 Result = match(s, p, i, j + 2) || (FirstMatch && match(s, p, i + 1, j)); 18 UsedPairs[PairToInt(i, j)] = Result; 19 return Result; 20 } 21 else { 22 Result = FirstMatch && match(s, p, i + 1, j + 1); 23 UsedPairs[PairToInt(i, j)] = Result; 24 return Result; 25 } 26 } 27 28 bool isMatch(string s, string p) { 29 slen = s.length(); 30 plen = p.length(); 31 if(slen==0 && plen==0) return true; 32 UsedPairs = (int*)malloc((slen + 1) * (plen + 1) * sizeof(int)); 33 memset(UsedPairs, -1, sizeof(UsedPairs)); 34 35 return match(s, p, 0, 0); 36 } 37 };
LC10-Regular Expression Matching
原文：https://www.cnblogs.com/osoii/p/12970073.html
