Leetcode-10-正则表达式匹配

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 <= 20
• 0 <= p.length <= 30
• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
• 保证每次出现字符 * 时，前面都匹配到有效的字符

10. Regular Expression Matching

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 <= 20
• 0 <= p.length <= 30
• s contains only lowercase English letters.
• p contains 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