10. 正则表达式匹配
难度困难
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
-
'.'匹配任意单个字符 -
'*'匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 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 = "c*a*b"
输出：true
解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5：
输入：s = "mississippi" p = "mis*is*p*."
输出：false
提示：
0 <= s.length <= 200 <= p.length <= 30-
s可能为空，且只包含从a-z的小写字母。 -
p可能为空，且只包含从a-z的小写字母，以及字符.和*。 - 保证每次出现字符
*时，前面都匹配到有效的字符
Hard
5669845Add to ListShare
Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*' where:
-
'.'Matches any single character. -
'*'Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Example 1:
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:
Input: s = "aab", p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
Example 5:
Input: s = "mississippi", p = "mis*is*p*."
Output: false
Constraints:
0 <= s.length <= 200 <= p.length <= 30-
scontains only lowercase English letters. -
pcontains only lowercase English letters,'.', and'*'. - It is guaranteed for each appearance of the character
'*', there will be a previous valid character to match.
image-20210424091755560
image-20210424091917775
image-20210424092123713
image-20210424092405388
解题思路，动态规划模型，一个样本做行，一个样本做列。
先对输入的string和匹配的pattern串进行有效性检查
public static boolean isValid(char[] str, char[] pattern) {
for (char cha : str) {
if (cha == '.' || cha == '*') {
return false;
}
}
for (int i = 0; i < pattern.length; i++) {
if (pattern[i] == '*' && (i == 0 || pattern[i - 1] == '*')) {
return false;
}
}
return true;
}
原字符串中不能有'.'和'*'
匹配穿不能是'*'开头和**
递归解决动态规划
一个样本做行，一个样本做列的动态规划模型
使用递归解决动态规划，递归函数boolean process(str, si, pattern,pi) 定义f函数 str[si,str.length)能够被 pattern[pi,pattern.length)匹配出来，如果能够递归出来return true
// str[si.....] 能否被 pattern[pi...] 变出来
// 潜台词：pi位置，pattern[pi] != '*'
public static boolean process(char[] str, char[] pattern, int si, int pi) {
if (si == str.length) { // si越界了
if (pi == pattern.length) {
return true;
}
if (pi + 1 < pattern.length && pattern[pi + 1] == '*') {
return process1(str, pattern, si, pi + 2);
}
return false;
}
// si 没越界
if (pi == pattern.length) {
return si == str.length;
}
// si 没越界 pi 没越界
if (pi + 1 >= pattern.length || pattern[pi + 1] != '*') {
return ((str[si] == pattern[pi]) || (pattern[pi] == '.')) && process1(str, pattern, si + 1, pi + 1);
}
// si 没越界 pi 没越界 pi+1 *
if (pattern[pi] != '.' && str[si] != pattern[pi]) {
return process1(str, pattern, si, pi + 2);
}
// si 没越界 pi 没越界 pi+1 * [pi]可配[si]
if (process1(str, pattern, si, pi + 2)) {//0份的情况 pattern[pi,pi+1]==""
return true;
}
while (si < str.length && (str[si] == pattern[pi] || pattern[pi] == '.')) {
if (process1(str, pattern, si + 1, pi + 2)) {
return true;
}
si++;
}
return false;
}
因为一个匹配串的第一个字符不能是* ，'*' 匹配零个或多个前面的那一个元素，*必须和前面一个字符配合使用，所以process函数的pattern[pi] != '*'
base case 1：si == str.length
先看process递归结束的条件(si == str.length) 原串此时匹配的串变为“ ”空字符串，如果pi == pattern.length则return true
只有pi+1="*" pi和pi+1才能匹配""空串。(pi + 1 < pattern.length && pattern[pi + 1] == '*')继续递归处理
image-20210424100320235
base case 2：pi == pattern.length
输入串 为空串，匹配串是空串才能匹配
base case 3：si 没越界 pi 没越界
image-20210424102013367
base case 4：si 没越界 pi 没越界，且pattern[pi+1]=*
image-20210424102538474
image-20210424103758508
base case 5：si 没越界 pi 没越界 pi+1 * [pi]可配[si]
a*变0个a
a*变1个a
image-20210424104842748
image-20210424104915361
所有可能性都要去递归
// si 没越界 pi 没越界 pi+1 * [pi]可配[si]
if (process1(str, pattern, si, pi + 2)) {//0份的情况 pattern[pi,pi+1]==""
return true;
}
while (si < str.length && (str[si] == pattern[pi] || pattern[pi] == '.')) {
if (process1(str, pattern, si + 1, pi + 2)) {
return true;
}
si++;
}
完整代码1：
class Solution {
public static boolean isValid(char[] str, char[] pattern) {
for (char cha : str) {
if (cha == '.' || cha == '*') {
return false;
}
}
for (int i = 0; i < pattern.length; i++) {
if (pattern[i] == '*' && (i == 0 || pattern[i - 1] == '*')) {
return false;
}
}
return true;
}
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
char[] str = s.toCharArray();
char[] pattern = p.toCharArray();
return isValid(str, pattern) && process1(str, pattern, 0, 0);
}
// str[si.....] 能否被 pattern[pi...] 变出来
// 潜台词：pi位置，pattern[pi] != '*'
public static boolean process1(char[] str, char[] pattern, int si, int pi) {
if (si == str.length) { // si越界了
if (pi == pattern.length) {
return true;
}
if (pi + 1 < pattern.length && pattern[pi + 1] == '*') {
return process1(str, pattern, si, pi + 2);
}
return false;
}
// si 没越界
if (pi == pattern.length) {
return si == str.length;
}
// si 没越界 pi 没越界
if (pi + 1 >= pattern.length || pattern[pi + 1] != '*') {
return ((str[si] == pattern[pi]) || (pattern[pi] == '.')) && process1(str, pattern, si + 1, pi + 1);
}
// si 没越界 pi 没越界 pi+1 * 后面条件一定是pattern[pi+1]== *
if (pattern[pi] != '.' && str[si] != pattern[pi]) {
return process1(str, pattern, si, pi + 2);
}
// si 没越界 pi 没越界 pi+1 * [pi]可配[si]
if (process1(str, pattern, si, pi + 2)) {
return true;
}
while (si < str.length && (str[si] == pattern[pi] || pattern[pi] == '.')) {
if (process1(str, pattern, si + 1, pi + 2)) {
return true;
}
si++;
}
return false;
}
}
image-20210424105936970
改动态规划
二维数组做缓存
public boolean isMatch2(String s, String p) {
if (s == null || p == null) {
return false;
}
char[] str = s.toCharArray();
char[] pattern = p.toCharArray();
int[][] dp = new int[str.length + 1][pattern.length + 1];
for (int si = 0; si <= str.length; si++) {
for (int pi = 0; pi <= pattern.length; pi++) {
dp[si][pi] = -1;
}
}
// dp[si][pi] == -1 //表示没有计算过
// dp[si][pi] == 0 si pi false 表示没有计算过，不匹配
// dp[si][pi] == 1 si pi true 表示没有计算过，匹配
return isValid(str, pattern) && process2(str, pattern, 0, 0, dp);
}
public boolean isValid(char[] str, char[] pattern) {
for (char cha : str) {
if (cha == '.' || cha == '*') {
return false;
}
}
for (int i = 0; i < pattern.length; i++) {
if (pattern[i] == '*' && (i == 0 || pattern[i - 1] == '*')) {
return false;
}
}
return true;
}
// str[si.....] 能否被 pattern[pi...] 变出来
// 潜台词：pi位置，pattern[pi] != '*'
public boolean process2(char[] str, char[] pattern, int si, int pi, int[][] dp) {
if (dp[si][pi] != -1) {
return dp[si][pi] == 1;
}
// si pi 这个参数组合第一次算
if (si == str.length) { // si越界了
if (pi == pattern.length) {
dp[si][pi] = 1;
return true;
}
// (pi pi+1) pi+2 ....
if (pi + 1 < pattern.length && pattern[pi + 1] == '*') {
boolean ans = process2(str, pattern, si, pi + 2, dp);
dp[si][pi] = ans ? 1 : 0;
return ans;
}
dp[si][pi] = 0;
return false;
}
// si 没越界
if (pi == pattern.length) {
boolean ans = si == str.length;
dp[si][pi] = ans ? 1 : 0;
return ans;
}
// si 没越界 pi 没越界
if (pi + 1 >= pattern.length || pattern[pi + 1] != '*') {
boolean ans = ((str[si] == pattern[pi]) || (pattern[pi] == '.'))
&& process2(str, pattern, si + 1, pi + 1, dp);
dp[si][pi] = ans ? 1 : 0;
return ans;
}
// si 没越界 pi 没越界 pi+1 *
if (pattern[pi] != '.' && str[si] != pattern[pi]) {
boolean ans = process2(str, pattern, si, pi + 2, dp);
dp[si][pi] = ans ? 1 : 0;
return ans;
}
if (process2(str, pattern, si, pi + 2, dp)) {
dp[si][pi] = 1;
return true;
}
while (si < str.length && (str[si] == pattern[pi] || pattern[pi] == '.')) {
if (process2(str, pattern, si + 1, pi + 2, dp)) {
dp[si][pi] = 1;
return true;
}
si++;
}
dp[si][pi] = 0;
return false;
}
image-20210424111523924
