[LeetCode HARD] 10 Regular Expression Matching

LeetCode has become the de facto go-to website for tech interviews. As a former competitive programmer, the LeetCode “hard”, “medium”, and “easy” problems are more like “easy”, “very easy”, “extremely easy” for me. I think it would be a good idea for me to put my solutions of some of the LeetCode hard problems here. Hope it would be helpful for people who are preparing for tech interviews.

This is my second LeetCode solution article, for LeetCode Problem 10, Regular Expression Matching.

Problem

Given an alphabet string and a simplified version of regular expression. Check if the string match the regular expression.

In the simplified version of regular expressions, there are only three type of elements: (1) a letter, matching a letter, (2) a dot, matching any letter (3) a letter or a dot followed by a star, matching zero or more copies of that letter, or any letter if it’s a dot.

Solution

This is a typical DP problem. Let f(i,j) be whether the prefix of length i of the string match the prefix of length j of the regular expression.

The base case is f(0,0)=true.

For the recursive step, if the j-th element of is a letter or a dot, then we simply check if the i-th element of the string matches and check if f(i-1, j-1) is true.

If the j-th element of is a star, then we check f(i, j-2) to see if we can match the string without that star, and then we check if the (i-1)-th element matches and check f(j-1, j) is true.

Source Code

The source code is in C++. Instead of writing in a recursive manner, I wrote the program in the other direction because it’s easier to write.

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