Regular Expression Matching: Recursive and DP-based implementation

Question

Problem Statement:

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

The function prototype should be:

bool isMatch(const char *s, const char *p)

Some examples:

isMatch("aa","a") ? false isMatch("aa","aa") ? true isMatch("aaa","aa") ? false

isMatch("aa", "a*") ? true

isMatch("aa", ".*") ? true

isMatch("ab", ".*") ? true

isMatch("aab", "c*a*b") ? true

I have two Java implementations; one uses recursion (complexity \$O(2^{m+n})\$) , the other dynamic programming (complexity \$O(mn)\$).

I am looking for feedbacks on how to write better, more elegant code. Any suggestions on style, simplicity, comments, etc., are welcome.

Assumptions I made:

1. s is a valid string not including '.'and '*'
2. p is a legal regular expression

Recursive version:

public class Solution {
    static public boolean charMatch(char c, char p){
        return c == p || p == '.';
    }

    static public boolean nextStar(String p, int pIdx){
        if(pIdx + 1 >= p.length()){
            return false;
        }
        return p.charAt(pIdx+1) == '*';
    }


    static public boolean partialMatch(String s, int sIdx, String p, int pIdx){
        //an empty pattern only matches empty string
        if(pIdx == p.length()){
            return sIdx == s.length();
        }

        //pattern starts with 'x*', check if we can simply skip it and still match
        if(nextStar(p, pIdx)) {
            if (partialMatch(s, sIdx, p, pIdx + 2)) return true;
    };

        //empty string, but cannot match the pattern by skipping the 'x*' pattern, so match fails
        if(sIdx == s.length()) return false;

        //match first character and see if the rest matches
        if(nextStar(p, pIdx)) {
           return charMatch(s.charAt(sIdx), p.charAt(pIdx)) && partialMatch(s, sIdx + 1, p, pIdx);
        }
        return charMatch(s.charAt(sIdx), p.charAt(pIdx)) && partialMatch(s, sIdx + 1, p, pIdx+1);
    }

    static public boolean isMatch(String s, String p) {
        return partialMatch(s, 0, p, 0);
    }

}

DP version:

public class RegularExpressionSolution5 {
    static private boolean charMatch(char c, char p){
        return c == p || p == '.';
    }

    static private boolean nextStar(String p, int pIdx){
        if(pIdx + 1 >= p.length()){
            return false;
        }
        return p.charAt(pIdx+1) == '*';
    }


    // matchMatrix[x][y] --> if s.substr(x, s.length) matches p.substr(y, p.length)
    // note that p.substr(y, p.length) may not be a valid regular expression (starts with '*'),
    // in which case the matrix is filled with false
    static public void fillMatchMatrix(String s, String p, boolean[][] matchMatrix){
        for(int sIdx = s.length(); sIdx >= 0; sIdx--){
            for(int pIdx = p.length(); pIdx >= 0; pIdx--){
                //an empty pattern only matches empty string
                if(pIdx == p.length()){
                    matchMatrix[sIdx][pIdx] = (sIdx == s.length());
                    continue;
                }

                //pattern starts with 'x*', check if we can simply skip it and still match
                if(nextStar(p, pIdx) && matchMatrix[sIdx][pIdx+2] == true){
                    matchMatrix[sIdx][pIdx] = true;
                    continue;
                }

                //empty string, but cannot match the pattern by skipping the 'x*' pattern, so match fails
                if(sIdx == s.length()) {
                    matchMatrix[sIdx][pIdx] = false;
                    continue;
                }

                //match first character and see if next matches
                if(nextStar(p, pIdx)){
                    matchMatrix[sIdx][pIdx] = charMatch(s.charAt(sIdx), p.charAt(pIdx)) && matchMatrix[sIdx+1][pIdx];
                }else{
                    matchMatrix[sIdx][pIdx] = charMatch(s.charAt(sIdx), p.charAt(pIdx)) && matchMatrix[sIdx+1][pIdx+1];
                }
            }
        }
    }

    static public boolean isMatch(String s, String p) {
        boolean[][] matchMatrix = new boolean[s.length()+1][p.length()+1];
        fillMatchMatrix(s, p, matchMatrix);
        return matchMatrix[0][0];
    }

}

Answer 1

I am looking for feedbacks on how to write better, more elegant code. Any suggestions on style, simplicity, comments, etc., are welcome.

Recursive:

public class Solution {
    static public boolean charMatch(char c, char p){

Readability-wise, it would be nice if I didn't have to look at other parts of the code to know what c and p are. Consider giving them more descriptive names.

        return c == p || p == '.';
    }

    static public boolean nextStar(String p, int pIdx){

I would consider naming this function nextIsStar to reflect that it returns a boolean answer

        if(pIdx + 1 >= p.length()){
            return false;
        }
        return p.charAt(pIdx+1) == '*';
    }


    static public boolean partialMatch(String s, int sIdx, String p, int pIdx){
        //an empty pattern only matches empty string
        if(pIdx == p.length()){
            return sIdx == s.length();
        }

        //pattern starts with 'x*', check if we can simply skip it and still match
        if(nextStar(p, pIdx)) {
            if (partialMatch(s, sIdx, p, pIdx + 2)) return true;
    };

You don't need a semi colon here, and the curly brace is indented strangely

        //empty string, but cannot match the pattern by skipping the 'x*' pattern, so match fails
        if(sIdx == s.length()) return false;

        //match first character and see if the rest matches
        if(nextStar(p, pIdx)) {
           return charMatch(s.charAt(sIdx), p.charAt(pIdx)) && partialMatch(s, sIdx + 1, p, pIdx);
        }
        return charMatch(s.charAt(sIdx), p.charAt(pIdx)) && partialMatch(s, sIdx + 1, p, pIdx+1);
    }

As the main function, i.e. the one the user will actually call, this should be commented.

    static public boolean isMatch(String s, String p) {
        return partialMatch(s, 0, p, 0);
    }

Overall: isMatch() should be the only public method - the others are helper functions to its functionality. Assuming you don't expect someone to re-use their functionality in another program, they should be private. Also, isMatch() should be the first thing in the file, with the other methods below it; as a general rule, if method A calls helper method B, B should come after A.

This solution is very clean, and you did a good job separating the logic into intuitive pieces for each function.

DP:

public class RegularExpressionSolution5 {
    static private boolean charMatch(char c, char p){
        return c == p || p == '.';

As above, p and c names

    }

    static private boolean nextStar(String p, int pIdx){

Also as above

        if(pIdx + 1 >= p.length()){
            return false;
        }
        return p.charAt(pIdx+1) == '*';
    }


    // matchMatrix[x][y] --> if s.substr(x, s.length) matches p.substr(y, p.length)

This comment could be clearer. Perhaps "matchMatrix[x][y] is true if s.substr..."

    // note that p.substr(y, p.length) may not be a valid regular expression (starts with '*'),
    // in which case the matrix is filled with false

This is a nice robustness measure, but make sure you think about whether, in production, you'd want this or an "Invalid Regex" exception. It's good to communicate to an interviewer that you think about the impact and tradeoffs inherent in your coding decisions. An exception might save someone a lot of headaches later on, instead of leaving them wondering why their string search always returns 0 matching results.

    static public void fillMatchMatrix(String s, String p, boolean[][] matchMatrix){

This method is huge and hard to understand, which is typical of DP solutions. Think about whether you could break out some parts of the double loop - maybe even the entire internal loop, and place them in helper functions with easy to understand names, so that what's left in this function is intuitive, quick to understand, and short.

        for(int sIdx = s.length(); sIdx >= 0; sIdx--){
            for(int pIdx = p.length(); pIdx >= 0; pIdx--){
                //an empty pattern only matches empty string
                if(pIdx == p.length()){
                    matchMatrix[sIdx][pIdx] = (sIdx == s.length());
                    continue;
                }

                //pattern starts with 'x*', check if we can simply skip it and still match
                if(nextStar(p, pIdx) && matchMatrix[sIdx][pIdx+2] == true){
                    matchMatrix[sIdx][pIdx] = true;
                    continue;
                }

                //empty string, but cannot match the pattern by skipping the 'x*' pattern, so match fails
                if(sIdx == s.length()) {
                    matchMatrix[sIdx][pIdx] = false;
                    continue;
                }

                //match first character and see if next matches
                if(nextStar(p, pIdx)){
                    matchMatrix[sIdx][pIdx] = charMatch(s.charAt(sIdx), p.charAt(pIdx)) && matchMatrix[sIdx+1][pIdx];
                }else{
                    matchMatrix[sIdx][pIdx] = charMatch(s.charAt(sIdx), p.charAt(pIdx)) && matchMatrix[sIdx+1][pIdx+1];
                }
            }
        }
    }

    static public boolean isMatch(String s, String p) {

As above, this should be commented

        boolean[][] matchMatrix = new boolean[s.length()+1][p.length()+1];
        fillMatchMatrix(s, p, matchMatrix);
        return matchMatrix[0][0];
    }

}

Overall: as in the first program, helper methods should be private and placed below the main method that actually runs all the functionality. This is an impressive solution, and aside from the one long method, very clean.

If you want more advice on code formatting, naming conventions, and program structure, you can look at the book Clean Code by Robert Martin ("Uncle Bob"), on Amazon here. (And available as a free PDF online, somewhere).

EDIT: How I would refactor the double loop:

First, pull out the interior loop, replace it with a function we'll define later. Also, rename some variables to make it more readable. sIdx becomes rowNum, and s.length() is saved as numOfRows:

final int numOfRows = s.length();
for(int rowNum = numOfRows; rowNum >= 0; rowNum--){
    fillRow(rowNum);
}

The goal in the above is to make it so that the reader understands what this code is doing before looking at the fillRow() function itself.

Now we look at what we pulled out:

private void fillRow(int rowNum) {
    final int numOfCols = p.length();
    for(int colNum = numOfCols; colNum >= 0; colNum--){
        fillCell(rowNum, colNum);
    }
}

Similar to the above, I renamed some variables. Notice that each of the previous two code snippets does one thing: the first loop fills the whole table, row by row. The function it calls fills a single row, column by column. The function it calls fills a single cell, checking each possible condition to decide how to fill the cell.

private void fillCell(sIdx, pIdx) {
    //an empty pattern only matches empty string
    if(pIdx == p.length()){
        matchMatrix[sIdx][pIdx] = (sIdx == s.length());
        continue;
    }

    //pattern starts with 'x*', check if we can simply skip it and still match
    if(nextStar(p, pIdx) && matchMatrix[sIdx][pIdx+2] == true){ // NOTE: == true is always redundant. Can you see why?
        matchMatrix[sIdx][pIdx] = true;
        continue;
    }

    //empty string, but cannot match the pattern by skipping the 'x*' pattern, so match fails
    if(sIdx == s.length()) {
        matchMatrix[sIdx][pIdx] = false;
        continue;
    }

    //match first character and see if next matches
    if(nextStar(p, pIdx)){
        matchMatrix[sIdx][pIdx] = charMatch(s.charAt(sIdx), p.charAt(pIdx)) && matchMatrix[sIdx+1][pIdx];
    }else{
        matchMatrix[sIdx][pIdx] = charMatch(s.charAt(sIdx), p.charAt(pIdx)) && matchMatrix[sIdx+1][pIdx+1];
    }
}

Hope this is clear, and gives you some intuition. "Each function should do one thing" is a good rule of thumb, even for convoluted code like in DP. Please note: I did not run the above code, so it's possible (even probable, perhaps), that I made an error in refactoring. If you're gonna use it for something, test it!