Regular Expression Matching Regular Expression Matching LeetCode Solution

Difficulty Level Hard
Frequently asked in Adobe Airbnb Amazon Apple Bloomberg Coursera eBay Facebook Goldman Sachs Google JPMorgan Microsoft Nvidia Paytm Snapchat Twitter Uber YahooViews 2918

Problem Statement

Regular Expression Matching Regular Expression Matching LeetCode Solution – 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).

Regular Expression Matching Regular Expression Matching

Example

Test Case 1:

Input:

s = “aa”

p = “a”

Output:

false

Test Case 2:

Input:

s = “aa”

p = “a*”

Output:

true

Test Case 3:

Input:

s = “ab”

p = “.*”

Output:

true

Explanation:

i) “a” does not match the entire string “aa”.

ii) ‘*’ means zero or more of the preceding element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”.

iii) “.*” means “zero or more (*) of any character (.)”.

Approach:

s=’aab’, p=’c*a*b’

c * a * b

0 1 2 3 4 5

0 y

a 1

a 2

b 3

dp[i][j] denotes if s.substring(0,i) is valid for pattern p.substring(0,j). For example dp[0][0] == true (denoted by y in the matrix) because when s and p are both empty they match. So if we somehow base dp[i+1][j+1] on previos dp[i][j]’s then the result will be dp[s.length()][p.length()].

So what about the first column? for an empty pattern p=””, the only thing that is valid is an empty string s=””, and that is already our dp[0][0] which is true. That means rest of `dp[i][0]’ is false.

s=’aab’, p=’c*a*b’

c * a * b

0 1 2 3 4 5

0 y

a 1 n

a 2 n

b 3 n

What about the first row? In other words which pattern p matches empty string s=””? The answer is either an empty pattern p=””, or a pattern that can represent an empty string such as p=”a*”, p=”z*” or more interestingly a combination of them as in p=”a*b*c*”. Below for loop is used to populate dp[0][j]. Note how it uses previous states by checking dp[0][j-2].

for (int j=2; j<=p.length(); j++) {

dp[0][j] = p.charAt(j-1) == ‘*’ && dp[0][j-2];

}

At this stage our matrix has become as follows: Notice dp[0][2] and dp[0][4] are both true because p=”c*” and p=”c*a*” can both match an empty string.

s=’aab’, p=’c*a*b’

c * a * b

0 1 2 3 4 5

0 y n y n y n

a 1 n

a 2 n

b 3 n

So now we can start our main iteration. It is basically the same, we will iterate all possible s lengths (i) for all possible p lengths (j) and we will try to find a relationship based on previous results. Turns out there are two cases.

  1. (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j-1) == ‘.’) if the current characters match or pattern has . then the result is determined by the previous state dp[i][j] = dp[i-1][j-1]. Don’t be confused by the charAt(j-1) charAt(i-1) indexes using a -1 offset that is because our dp array is actually one index bigger than our string and pattern lenghts to hold the initial state dp[0][0]
  2. if p.charAt(j-1) == ‘*’ then either it acts as an empty set and the result is dp[i][j] = dp[i][j-2] or (s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2) == ‘.’) current char of string equals the char preceding * in pattern so the result is dp[i-1][j].

So here is the final state of the matrix after we evaluate all elements:

s=’aab’, p=’c*a*b’

c * a * b

0 1 2 3 4 5

0 y n y n y n

a 1 n n n y y n

a 2 n n n n y n

b 3 n n n n n y

Code for Regular Expression Matching Regular Expression Matching

Java Program

class Solution {
    public boolean isMatch(String s, String p) {
        if (p == null || p.length() == 0) return (s == null || s.length() == 0);
        
        boolean dp[][] = new boolean[s.length()+1][p.length()+1];
        dp[0][0] = true;
        for (int j=2; j<=p.length(); j++) {
            dp[0][j] = p.charAt(j-1) == '*' && dp[0][j-2]; 
        }
        
        for (int j=1; j<=p.length(); j++) {
            for (int i=1; i<=s.length(); i++) {
                if (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j-1) == '.') 
          dp[i][j] = dp[i-1][j-1];
                else if(p.charAt(j-1) == '*')
                    dp[i][j] = dp[i][j-2] || ((s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2) == '.') && dp[i-1][j]); 
            }
        }
        return dp[s.length()][p.length()];
    }
}

C++ Program

class Solution {
public:
    bool isMatch(string s, string p) {
       int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int i = 0; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == '*') {
                    dp[i][j] = dp[i][j - 2] || (i && dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
                } else {
                    dp[i][j] = i && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
                }
            }
        }
        return dp[m][n]; 
    }
};

Complexity Analysis for Regular Expression Matching Regular Expression Matching LeetCode Solution

Time Complexity: O(p.length() * s.length()).

Space Complexity: O(p.length() * s.length()).

Translate »