Concise Recursive DP Solution with Recurrence Relation Defined


  • 0

    Let's establish some rules. dp[m][n] returns a boolean. It tells us whether the regular expression of length n matches the word of length m.

    Now onto base case.

    dp[0][0] will always be true.
    dp[n][0], where n > 0, will always be false. Empty expressions match nothing.
    dp[0][n] can either be true for false. If the character at n is '', dp[0][n] will match dp[0][n-2]. This is to handle the edge case where regex "abc.*" can match an empty string.

    Okay, now onto the recurrence relationship!!

    dp[i][j] = if str[i] == pattern[j] or pattern[j] == '.'
                         dp[i][j] = dp[i-1][j-1]
                 if pattern[j] == '*'
                         dp[i][j] = dp[i-2][j] 
                         also if str[i] == pattern[j-1] or pattern[j-1] == '.'
                         dp[i][j] = dp[i][j] | dp[i-1][j] 
    

    So what the heck is going on? I'll break it down. It's quite simple.

    In the first if - if the characters match or if the pattern is a wildcard char, then reduce pattern and word by length of 1, and see if they match before. If they matched before, then adding the same character to both or a wildcard to pattern won't change the result.

    In the second if - when we get a '*' for our pattern, we need to check for two cases.

    1. For if the wild card matches nothing. We need to reduce our word by length of two, and see if it matches our current pattern. (ex. abb will match abbc*)
    2. If our current string character is equal to the previous character of our pattern, or if that previous character is a wild card character, then we can simply check if it matches with one or more of that character. We do this by reducing the length of string by 1.

    Otherwise, everything else is false.

    Below is the implementation. Enjoy!

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.