Regular expressions

Dynamic programming questions scared the crap out of me before. Not any longer... After my vacay 😎 I am feeling more confident than ever in solving them.

The last week was a hectic one, since I had to catch up at work and also I needed to deliver one key functionality in the first two days of the work-week.

BACK TO QUESTION. This question was a slightly tricky to put into recursion loop...

Recursive function

C(i, j) = C(i, j+2) || # ignore pattern `(something)*`
          (C(i+1, j) && (str[i] == pat[j] || str[i] == '.')), pat[j+1] == '*' # include pattern `(sth)*` in match and check for remaining sub-string for match with `(sth)*` included
        = C(i+1, j+1), (str[i] == pat[j] || str[i] == '.') # simple char match at positions `i` and `j`
        = false, in any other case

On deeper analysis or with an example it becomes clear that this recursion function satisfies both overlapping subproblems and optimal substructure property. And so we can memoize solutions to sub-problems for repeated use.

Code here 👨‍💻 - for top-down DP

We have used int array for keeping track of unvisited combinations(by setting them to 0 as default, 1 for true and -1 for false).

java
class Solution {
    
    private int [][]answers;
    private char[] str;
    private char[] pat;
    public boolean isMatch(String str, String pattern) {
        answers = new int[str.length()+1][pattern.length()+1];
        this.str = str.toCharArray();
        this.pat = pattern.toCharArray();
        return isMatchMemoised(0, 0);
    }

    public boolean isMatchMemoised(int i, int j){
        if(answers[i][j] != 0){
            return answers[i][j] == 1;
        }
      
        if(pat.length == j) { // reached the end of pattern
            // either reached string end or some pattern already matches
            answers[i][j] = (str.length == i || (answers[i][j] == 1))? 1:-1; 
        } else {
            // match with current
            boolean currMatch = i<str.length && (str[i] == pat[j] || pat[j] == '.');
            if ( (j+1)<pat.length && pat[j+1] == '*'){ // match with next *
                answers[i][j] = isMatchMemoised(i, j+2) || // ignoring *
                    (currMatch && isMatchMemoised(i+1, j)) ?
                    1: -1; // use * with next char in `str`
            } else { // match with next
                answers[i][j] = currMatch && isMatchMemoised(i+1, j+1)? 1:-1;
            }
        }

        return answers[i][j] == 1;

    }
}

Time and memory complexity: O(m*n)

There's a similar problem to this one on Leetcode and you can find it here

Cheers guys be awesome...👋