剑指 Offer 19. 正则表达式匹配
正则表达式 匹配 Offer 19
2023-09-11 14:19:00 时间
思路
方法一:递归
以下代码改成c++中string的写法,提交到C++中会超时,可能string比指针更慢吧。
以下C语言代码参考《剑指offer(第2版)》书中的代码,可以在leetcode中提交通过。
这种递归方法效率比较低下。
1 bool matchCore(const char* str, const char* pattern) 2 { 3 if(*str == '\0' && *pattern == '\0') 4 return true; 5 6 if(*str != '\0' && *pattern == '\0') 7 return false; 8 9 if(*(pattern + 1) == '*') 10 { 11 if(*pattern == *str || (*pattern == '.' && *str != '\0')) 12 // '*'不重复 13 return matchCore(str + 1, pattern + 2) 14 // '*'继续重复 15 || matchCore(str + 1, pattern) 16 // '*'重复0次 17 || matchCore(str, pattern + 2); 18 else 19 // '*'重复0次 20 return matchCore(str, pattern + 2); 21 } else if(*str == *pattern || (*pattern == '.' && *str != '\0')) 22 return matchCore(str + 1, pattern + 1); 23 24 return false; 25 } 26 27 bool isMatch(char* s, char* p){ 28 if(s == NULL || p == NULL) 29 return false; 30 31 return matchCore(s, p); 32 }
方法二:动态规划
1 class Solution { 2 public: 3 bool isMatch(string s, string p) { 4 int m = s.size(); 5 int n = p.size(); 6 7 vector<vector<bool>> f(m + 1, vector<bool>(n + 1)); 8 f[0][0] = true; 9 for (int i = 0; i <= m; ++i) { 10 for (int j = 1; j <= n; ++j) { 11 if (p[j - 1] == '*') { 12 f[i][j] = f[i][j - 2]; 13 if (matches(s, p, i, j - 1)) { 14 f[i][j] = f[i][j] || f[i - 1][j]; 15 } 16 } 17 else { 18 if (matches(s, p, i, j)) { 19 f[i][j] = f[i - 1][j - 1]; 20 } 21 } 22 } 23 } 24 return f[m][n]; 25 } 26 27 //注意i,j与下标之间的对应关系 28 bool matches(string &s, string &p, int i, int j) { 29 if (i == 0) { 30 return false; 31 } 32 if (p[j - 1] == '.') { 33 return true; 34 } 35 return s[i - 1] == p[j - 1]; 36 }; 37 };
参考
相关文章
- 正则表达式入门(三)边界
- Java利用正则表达式实现中英文日期转换函数封装
- JavaScript 19. 正则表达式
- 匹配java double值的正则表达式
- 正则表达式匹配a标签的href
- Java 日期时间与正则表达式,超详细整理,适合新手入门
- 《正则表达式经典实例(第2版)》——2.3 匹配多个字符之一
- 《正则表达式经典实例(第2版)》——2.4 匹配任意字符
- 《正则表达式经典实例(第2版)》——2.21 把部分的正则匹配添加到替代文本中
- Python 正则表达式语法实例
- JavaScript+Regex 身份证号码的正则表达式及验证详解
- python2.7 正则表达式的学习
- 正则表达式小记--匹配但不获取
- Java中正则表达式、模式匹配与信息抽取
- java 使用正则表达式过滤HTML中标签
- 《剑指offer》-- 数组中的逆序对、最小的K个数、从1到n整数中1出现的次数、正则表达式匹配、数值的整数次方
- 正则表达式
- python五十六课——正则表达式(常用函数之findall)
- Jmeter入门—正则表达式提取器(神器)
- 正则表达式 巩固
- 正则表达式_合集下(后续还会有补充)