首页 > 其他 > 详细

LC10-Regular Expression Matching

时间:2020-05-27 10:05:18      阅读:43      评论:0      收藏:0      [点我收藏+]

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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!