Leecode刷题之路第十天之正则表达式匹配

题目出处

10-正则表达式匹配

题目描述

个人解法

思路：

todo

代码示例：（Java）

todo

复杂度分析

todo

官方解法

10-正则表达式匹配-官方解法

方法1：动态规划

思路：

代码示例：（Java）

public boolean isMatch(String s, String p) {int m = s.length();int n = p.length();boolean[][] f = new boolean[m + 1][n + 1];f[0][0] = true;for (int i = 0; i <= m; ++i) {for (int j = 1; j <= n; ++j) {if (p.charAt(j - 1) == '*') {f[i][j] = f[i][j - 2];if (matches(s, p, i, j - 1)) {f[i][j] = f[i][j] || f[i - 1][j];}} else {if (matches(s, p, i, j)) {f[i][j] = f[i - 1][j - 1];}}}}return f[m][n];}public boolean matches(String s, String p, int i, int j) {if (i == 0) {return false;}if (p.charAt(j - 1) == '.') {return true;}return s.charAt(i - 1) == p.charAt(j - 1);}

复杂度分析

考察知识点

1.正则表达式概念

正则表达式

收获

1.好多经典算法都可以自己实现一把，比如jdk，spring，hutool等很多的工具类都可以自己照着实现一波

Gitee源码位置

10-正则表达式匹配-源码

同名文章，已同步发表于CSDN，个人网站，公众号

• CSDN
  
  工一木子
• 个人网站
  
  工藤新一
• 公众号