Solution For Regular Expression Matching

Problem Statement

Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’.

‘.’ Matches any single character.

‘*’ Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:
Input: s = “aa”, p = “a”
Output: false
Explanation: “a” does not match the entire string “aa”.

Example 2:
Input: s = “aab”, p = “cab”
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, “cab” matches “aab”.

Solution

To solve this problem, we can use a dynamic programming approach. We can create a two-dimensional boolean array dp, where dp[i][j] represents whether the substring of s from 0 to i-1 can be matched with the substring of p from 0 to j-1.

Here are the steps to fill out the dp array:

1. Initialize dp[0][0] as true since an empty string can match another empty string.
2. Fill in the first row dp[0][j] according to the pattern. If p[j-1] is ‘‘, then dp[0][j] is equal to dp[0][j-2] (because ”” means zero or more of the preceding element).
3. Fill in the first column dp[i][0] as false since a non-empty string cannot match an empty pattern.
4. For each dp[i][j], if s[i-1] == p[j-1] or p[j-1] == ‘.’, we can match the characters. Therefore, dp[i][j] is equal to dp[i-1][j-1].
5. If p[j-1] == ‘‘, there are two cases to consider:
   a) if p[j-2] == s[i-1] or p[j-2] == ‘.’, the ‘‘ can either match zero or more characters. Therefore, we need to check dp[i][j-2] (zero match) or dp[i-1][j] (one or more matches)
   b) if p[j-2] != s[i-1], the ‘*’ can only match zero characters. Therefore, dp[i][j] is equal to dp[i][j-2]

Finally, we return dp[m][n], where m and n are the lengths of s and p respectively.

Here is the Python code for the solution:

class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
dp = [[False] * (n + 1) for _ in range(m + 1)] dp[0][0] = True

    # Fill in the first row dp[0][j]
    for j in range(2, n + 1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-2]

    # Fill in the first column dp[i][0]
    # (Already initialized as False)

    # Fill in the rest of the dp array
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i-1] == p[j-1] or p[j-1] == '.':
                dp[i][j] = dp[i-1][j-1]
            elif p[j-1] == '*':
                if p[j-2] == s[i-1] or p[j-2] == '.':
                    dp[i][j] = dp[i][j-2] or dp[i-1][j]
                else:
                    dp[i][j] = dp[i][j-2]

    return dp[m][n]

Time Complexity: O(mn), where m and n are the lengths of s and p respectively.
Space Complexity: O(mn), the size of the dp array.

Step by Step Implementation For Regular Expression Matching

public class Solution {
    public boolean isMatch(String s, String p) {
        // base case
        if (p.isEmpty()) return s.isEmpty();
        
        // special case
        if (p.length() == 1) {
        
            // if the length of s is 0, return false
            if (s.length() < 1) return false;
        
            //if the first does not match, return false
            else if ((p.charAt(0) != s.charAt(0)) && (p.charAt(0) != '.')) return false;
            
            // otherwise, compare the rest of the string of s and p.
            else return isMatch(s.substring(1), p.substring(1));
        }
        
        // case 1: when the second char of p is not '*'
        if (p.charAt(1) != '*') {
        
            if (s.isEmpty()) return false;
            if ((p.charAt(0) != s.charAt(0)) && (p.charAt(0) != '.')) return false;
            else return isMatch(s.substring(1), p.substring(1));
        }
        
        // case 2: when the second char of p is '*', complex case.
        else {
            //case 2.1: a char & '*' can stand for 0 element
            if (isMatch(s, p.substring(2))) return true;
            
            //case 2.2: a char & '*' can stand for 1 or more preceding element, 
            //so try every sub string
            int i = 0;
            while (i < s.length() && (s.charAt(i) == p.charAt(0) || p.charAt(0) == '.')) {
                if (isMatch(s.substring(i + 1), p.substring(2))) return true;
                i++;
            }
            return false;
        }
    }
}

def isMatch(s, p): 
    
    # Base Case 1: if both are empty 
    if not s and not p: 
        return True
    
    # Base Case 2: if one is empty 
    if not s or not p: 
        return False
    
    # match first characters and recur for the remaining 
    if s[0] == p[0] or p[0] == '.': 
        return isMatch(s[1:], p[1:]) 
    
    # If p's first character is '*', two cases arise: 
    # a) We consider the case where '*' matches with no character in s. 
    #    In this case, we recur for p[2:] 
    # b) '*' matches one or more characters in s 
    if p[0]=='*': 
        return isMatch(s, p[2:]) or isMatch(s[1:], p) 
    
    # If characters don't match 
    return False

var isMatch = function(s, p) {
    // your code goes here
};

class Solution {
public:
    bool isMatch(string s, string p) {
        
        // Base case
        if (p.empty()) return s.empty();
        
        // Special case
        if (p.size() == 1) {
            return (s.size() == 1 && (s[0] == p[0] || p[0] == '.'));
        }
        
        // If the second character is not '*'
        if (p[1] != '*') {
            if (s.empty()) return false;
            return (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
        }
        
        // If the second character is '*', complex case.
        while (!s.empty() && (s[0] == p[0] || p[0] == '.')) {
            if (isMatch(s, p.substr(2))) return true;
            s = s.substr(1);
        }
        
        // If there is a '*', we can ignore it and the character before it.
        return isMatch(s, p.substr(2));
    }
};

public class Solution {
    public bool IsMatch(string s, string p) {
        // base case
        if (p.Length == 0) return s.Length == 0;
        
        // special case
        if (p.Length == 1) {
        
            // if the length of s is 0, return false
            if (s.Length == 0) {
                return false;
            }
        
            //if the first does not match, return false
            else if ((p[0] != s[0]) && (p[0] != '.')) {
                return false;
            }
        
            // otherwise, compare the rest of the string of s and p.
            else {
                return IsMatch(s.Substring(1), p.Substring(1));
            }
        }
        
        // case 1: when the second char of p is not '*'
        if (p[1] != '*') {
            if (s.Length == 0) {
                return false;
            }
            if ((p[0] != s[0]) && (p[0] != '.')) {
                return false;
            }
            else {
                return IsMatch(s.Substring(1), p.Substring(1));
            }
        }
        
        // case 2: when the second char of p is '*', complex case.
        else {
            //case 2.1: a char & '*' can stand for 0 element
            if (IsMatch(s, p.Substring(2))) {
                return true;
            }
        
            //case 2.2: a char & '*' can stand for 1 or more preceding element, 
            //so try every sub string
            int i = 0;
            while (i