剑指 Offer 19. 正则表达式匹配（LeetCode 10）

原题链接

题目：

请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

示例 1:

输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入: s = "aa" p = "a*" 输出: true 解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

输入: s = "ab" p = "." 输出: true 解释: "." 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4:

输入: s = "aab" p = "cab" 输出: true 解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

输入: s = "mississippi" p = "misisp*." 输出: false

题解1：递归法（容易理解）

要点： 终止条件：如果正则串p为空字符串s也为空这匹配成功，如果正则串p为空但是s不是空则说明匹配失败 递归流程：

先匹配 s 和 p 的第一个字符 ，并设置 boolean 型标志变量接下来分情况讨论： 当 p 的第二个字符是 “*”，第一个字符可能需要匹配 0 次或多次 匹配 0 次 ，p 向后移动两位，再与 s 匹配匹配多次 ，首字符要匹配成功，再让 p 与 s 的下一位开始匹配即可 p 的第二个字符不是 “*”,判断第一个字符是否匹配即可，继续向下匹配或返回 false如果标志变量为 true ，则 s 和 p 向下一位匹配否则 p 的第二个字符不为 “*”，且 首字符不匹配即标志变量为 false，返回false

代码：

class Solution { public boolean isMatch(String s, String p) { if (p.isEmpty() && s.isEmpty()) return true; if (p.isEmpty() && !s.isEmpty()) return false; //此时 p 不为空，s 可能为空 boolean isMatched = !s.isEmpty() && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.'); if (p.length() >= 2 && p.charAt(1) == '*') { return (isMatch(s, p.substring(2))) || (isMatched && isMatch(s.substring(1), p)); } else if (isMatched) { return isMatch(s.substring(1), p.substring(1)); } else { return false; } } }

复杂度分析：

时间复杂度：O((n+m)*2^(n+m/2)) ，n和m分别是s和p的长度空间复杂度：O((n+m)*2^(n+m/2))

参考题解：

java回溯和动态规划，详细代码注释版本

题解2：记忆化递归

主要思路：

主要也是像上一个类似递归的想法首先要将递归参数改为 字符数组的下标索引然后建立一个记忆数组 mem 来记录结果，如果未匹配就记录 -1 ，匹配记录 1

代码：

class Solution { int[][] mem; public boolean isMatch(String s, String p) { mem = new int[s.length() + 1][p.length() + 1]; char[] sArray = s.toCharArray(); char[] pArray = p.toCharArray(); return dfs(sArray, 0, pArray, 0); } public boolean dfs(char[] s, int s1, char[] p, int p1) { if (p1 >= p.length && s1 >= s.length) return true; if (p1 >= p.length && s1 < s.length) return false; if (mem[s1][p1] != 0) return mem[s1][p1] == 1;//记忆化数组结果判断是否存在，有就直接取 //此时 p 不为空，s 可能为空 boolean isMatched = s1 < s.length && (p[p1] == s[s1] || p[p1] == '.'); if (p.length - p1 >= 2 && p[p1 + 1] == '*') { boolean ans = (dfs(s, s1, p, p1 + 2)) || (isMatched && dfs(s, s1 + 1, p, p1)); if (ans) mem[s1][p1] = 1; else mem[s1][p1] = -1; return ans; } else if (isMatched) { boolean ans = dfs(s, s1 + 1, p, p1 + 1); if (ans) mem[s1][p1] = 1; else mem[s1][p1] = -1; return ans; } else { return false; } } }

复杂度分析：

时间复杂度：O(mn)，相当于会把m * nm∗n的记忆数组遍历一遍。空间复杂度：O(mn)

参考题解：

java递归一步一步的优化到击败100%，以及动态规划，思路清晰

题解3：动态规划法

参考题解：

正则表达式匹配