Very Simple DP Solution in Java


  • 0
    B

    Set up a 2-D table dp[s.length() + 1][p.length() + 1] where dp[i][j] is whether [0, i - 1] of s can be matched by [0, j - 1] of p.
    dp[0][0] is true since the function returns true if both s and p are empty.
    dp[0][j] refers to if an empty s can be matched by [0, j - 1] of p.
    dp[i][0] refers to if [0, i - 1] of s can be matched by an empty p. All dp[i][0] values are false.

    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 <= p.length(); i++) {
                dp[0][i] = dp[0][i - 1] && (p.charAt(i - 1) == '*');
            }
            
            for (int i = 1; i <= s.length(); i++) {
                for (int j = 1; j <= p.length(); j++) {
                    if (p.charAt(j - 1) != '*') {
                        if (p.charAt(j - 1) == '?' || (p.charAt(j - 1) == s.charAt(i - 1))) {
                            dp[i][j] = dp[i - 1][j - 1];
                        }
                    } else {
                        dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                    }
                }
            }
            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.