Java DP solution, beat 99%!


  • 0

    Space complexity is O(m*n), might be optimized to O(min(m,n))
    Input is assumed to be always correctly formatted, so I did not check it in my code for simplicity.

        public boolean isMatch(String s, String p) {
            boolean dp[][] = new boolean[1+s.length()][1+p.length()];
            dp[0][0] = true;
            // Init First Row
            for (int j = 2; j < dp[0].length; j+=2) {
                if (p.charAt(j-1) == '*') dp[0][j] = dp[0][j-2];
            }
            // First Col default to false
            
            // Start DP here
            
            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];
                        } 
                    }
                }
            }
            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.