10. Regular Expression Matching – Leetcode Solutions

June 4, 2024

Table of Contents

Description:

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

Examples:

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

Solution in Python:

To implement the isMatch function that supports regular expression matching with . and * in Python, we can use dynamic programming. Here is a detailed implementation with comments explaining each step:

Python

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # Initialize a 2D DP table
        # dp[i][j] will be True if s[0..i-1] matches p[0..j-1]
        dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
        
        # Base case: Empty string matches with empty pattern
        dp[0][0] = True
        
        # Handle patterns with '*' at the beginning
        for j in range(1, len(p) + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]
        
        # Fill the DP table
        for i in range(1, len(s) + 1):
            for j in range(1, len(p) + 1):
                if p[j - 1] == s[i - 1] or p[j - 1] == '.':
                    # Characters match, or pattern has '.', copy the diagonal value
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == '*':
                    # Check zero occurrence of the character before '*'
                    dp[i][j] = dp[i][j - 2]
                    # Check one or more occurrence of the character before '*'
                    if p[j - 2] == s[i - 1] or p[j - 2] == '.':
                        dp[i][j] = dp[i][j] or dp[i - 1][j]

        return dp[len(s)][len(p)]

# Example usage:
solution = Solution()
print(solution.isMatch("aa", "a"))     # Output: False
print(solution.isMatch("aa", "a*"))    # Output: True
print(solution.isMatch("ab", ".*"))    # Output: True

Explanation:

Initialize the DP Table:
- We use a 2D list dp where dp[i][j] represents whether the substring s[0..i-1] matches the pattern p[0..j-1].
Base Case:
- dp[0][0] is True because an empty string matches an empty pattern.
Handle Patterns with ‘*’ at the Beginning:
- Patterns like a*, .*, a*b*c*, etc., can match an empty string, so we initialize the first row of the DP table accordingly.
Fill the DP Table:
- Iterate over each character in the string s and the pattern p to fill the DP table based on the following rules:
  - If the current characters match (p[j-1] == s[i-1]) or the pattern has a dot (p[j-1] == '.'), copy the diagonal value dp[i-1][j-1].
  - If the pattern character is *, check two conditions:
    - Zero occurrence of the character before * by copying the value from dp[i][j-2].
    - One or more occurrence of the character before * if it matches the current character in s or is a dot.
Return the Result:
- The value in dp[len(s)][len(p)] will indicate if the entire string s matches the pattern p.

This implementation efficiently handles all specified edge cases and constraints.

Solution in Javascript:

JavaScript

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
    // Initialize a 2D DP table
    // dp[i][j] will be true if s[0..i-1] matches p[0..j-1]
    const dp = Array(s.length + 1).fill(null).map(() => Array(p.length + 1).fill(false));
    
    // Base case: Empty string matches with empty pattern
    dp[0][0] = true;
    
    // Handle patterns with '*' at the beginning
    for (let j = 1; j <= p.length; j++) {
        if (p[j - 1] === '*') {
            dp[0][j] = dp[0][j - 2];
        }
    }
    
    // Fill the DP table
    for (let i = 1; i <= s.length; i++) {
        for (let j = 1; j <= p.length; j++) {
            if (p[j - 1] === s[i - 1] || p[j - 1] === '.') {
                // Characters match, or pattern has '.', copy the diagonal value
                dp[i][j] = dp[i - 1][j - 1];
            } else if (p[j - 1] === '*') {
                // Check zero occurrence of the character before '*'
                dp[i][j] = dp[i][j - 2];
                // Check one or more occurrence of the character before '*'
                if (p[j - 2] === s[i - 1] || p[j - 2] === '.') {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
            }
        }
    }
    
    return dp[s.length][p.length];
};

// Example usage:
console.log(isMatch("aa", "a"));     // Output: false
console.log(isMatch("aa", "a*"));    // Output: true
console.log(isMatch("ab", ".*"));    // Output: true

Solution in Java:

Java

class Solution {
    public boolean isMatch(String s, String p) {
        // Initialize a 2D DP table
        // dp[i][j] will be true if s[0..i-1] matches p[0..j-1]
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        
        // Base case: Empty string matches with empty pattern
        dp[0][0] = true;
        
        // Handle patterns with '*' at the beginning
        for (int j = 1; j <= p.length(); j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }
        
        // Fill the DP table
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= p.length(); j++) {
                if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '.') {
                    // Characters match, or pattern has '.', copy the diagonal value
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    // Check zero occurrence of the character before '*'
                    dp[i][j] = dp[i][j - 2];
                    // Check one or more occurrence of the character before '*'
                    if (p.charAt(j - 2) == s.charAt(i - 1) || p.charAt(j - 2) == '.') {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }
                }
            }
        }
        
        return dp[s.length()][p.length()];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        
        // Test cases
        System.out.println(solution.isMatch("aa", "a"));     // Output: false
        System.out.println(solution.isMatch("aa", "a*"));    // Output: true
        System.out.println(solution.isMatch("ab", ".*"));    // Output: true
        System.out.println(solution.isMatch("aab", "c*a*b")); // Output: true
        System.out.println(solution.isMatch("mississippi", "mis*is*p*.")); // Output: false
    }
}

Solution in C#:

C#

public class Solution {
    public bool IsMatch(string s, string p) {
        // Initialize a 2D DP table
        // dp[i][j] will be true if s[0..i-1] matches p[0..j-1]
        bool[,] dp = new bool[s.Length + 1, p.Length + 1];
        
        // Base case: Empty string matches with empty pattern
        dp[0, 0] = true;
        
        // Handle patterns with '*' at the beginning
        for (int j = 1; j <= p.Length; j++) {
            if (p[j - 1] == '*') {
                dp[0, j] = dp[0, j - 2];
            }
        }
        
        // Fill the DP table
        for (int i = 1; i <= s.Length; i++) {
            for (int j = 1; j <= p.Length; j++) {
                if (p[j - 1] == s[i - 1] || p[j - 1] == '.') {
                    // Characters match, or pattern has '.', copy the diagonal value
                    dp[i, j] = dp[i - 1, j - 1];
                } else if (p[j - 1] == '*') {
                    // Check zero occurrence of the character before '*'
                    dp[i, j] = dp[i, j - 2];
                    // Check one or more occurrence of the character before '*'
                    if (p[j - 2] == s[i - 1] || p[j - 2] == '.') {
                        dp[i, j] = dp[i, j] || dp[i - 1, j];
                    }
                }
            }
        }
        
        return dp[s.Length, p.Length];
    }
    
   
}

10. Regular Expression Matching – Leetcode Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Popular

84. Largest Rectangle in Histogram – Leetcode Solutions

222. Count Complete Tree Nodes – Leetcode Solutions

98. Validate Binary Search Tree – Leetcode Solutions

70. Climbing Stairs – Leetcode Solutions

Working with Files in Python

Convert Sorted Array to Binary Search Tree – Solutions

The fractions Module in Python

10. Regular Expression Matching – Leetcode Solutions

Description:

Solution in Python:

Solution in Javascript:

Solution in Java:

Solution in C#:

Related Post

Popular