10. Regular Expression Matching

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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 (.)".

Constraints:

• 1 <= s.length <= 20
• 1 <= 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.

Code

		x	a	*	b	.	c
	T	F	F	F	F	F	F
x	F	T	F	T	F	F	F
a	F	F	T	T	F	F	F
a	F	F	F	T	F	F	F
b	F	F	F	F	T	F	F
y	F	F	F	F	F	T	F
c	F	F	F	F	F	F	T

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;

        for(int i = 1; i <= n; i++){
            if(p.charAt(i - 1) =='*' && dp[0][i - 2] == true){
                dp[0][i] = true;
            }
        }

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(s.charAt(i - 1) == p.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1];
                }

                if (p.charAt(j - 1) =='.'){
                    dp[i][j] = dp[i - 1][j - 1];
                }

                if(p.charAt(j - 1) =='*'){
                    // p的前一个字符不能变成s的当前字符
                    // -> 只能删除p的前一个字符和p的当前字符, 看是不是可以匹配
                    if(p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.'){
                        dp[i][j] = dp[i][j - 2];
                    } else {
                        // p的前一个字符可以等于s的当前字符
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 1] || dp[i][j - 2];
                    }
                }
            }
        }

        return dp[m][n];
    }
}

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m = len(s)
        n = len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        for j in range(1, n + 1):
            if p[j - 1] == '*' and dp[0][j - 2]:
                dp[0][j] = True
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                a = s[i - 1]
                b = p[j - 1]
                if a == b or b == '.':
                    dp[i][j] = dp[i - 1][j - 1]
                if b == '*':
                    dp[i][j] = dp[i][j - 2]
                    if p[j - 2] == a or p[j - 2] == '.':
                        dp[i][j] = dp[i - 1][j] or dp[i][j - 1] or dp[i][j - 2]
        return dp[m][n]