Java DP Solution (6ms)


  • 0

    This dp idea is coming from WildCard Matching after painful thinking about initial state and when some char at p == '*'.
    For initial state I use a helper function to check if substring of p is empty.
    The meaning of match[i][j], i == 0 and j == 0 mean "" (empty string).
    The most interesting part is on some char == '*' in p.
    match[i][j] = match[i][j - 2] || (match[i - 1][j] && (p.charAt(j - 2) == '.' || s.charAt(i - 1) == p.charAt(j - 2)));
    match[i][j - 2] indicates the char == '*' in p and the char before it combines a empty string
    match[i - 1][j] means maybe the previous char at substring of s (0 ~ i - 2) can match current part of substring of p (0 ~ i - 1 ). So we need to know if s.charAt(i - 1) == p.charAt(i - 2) (which is the char before '*').

    It is a little confusing, just take a look at the code below:

    public class Solution {
        public boolean isMatch(String s, String p) {
            if (s == null || p == null) {
                return false;
            }
            boolean isEmpty = checkEmpty(p);
            if (s.length() == 0) {
               return isEmpty;
            }
            if (p.length() == 0) {
                return false;
            }
            boolean[][] match = new boolean[s.length() + 1][p.length() + 1];
            match[0][0] = true;
            for (int i = 1; i <= s.length(); i++) {
                match[i][0] = false;
            }
            for (int j = 1; j <= p.length(); j++) {
                match[0][j] = checkEmpty(p.substring(0, j));
            }
            
            for (int i = 1; i <= s.length(); i++) {
                for (int j = 1; j <= p.length(); j++) {
                    if (j != 1 && p.charAt(j - 1) == '*') {
                        match[i][j] = match[i][j - 2] || (match[i - 1][j] && 
                        (p.charAt(j - 2) == '.' || s.charAt(i - 1) == p.charAt(j - 2)));
                    }
                    else if (p.charAt(j - 1) == '.') {
                        match[i][j] = match[i - 1][j - 1];
                    }
                    else if (p.charAt(j - 1) == s.charAt(i - 1)) {
                        match[i][j] = match[i - 1][j - 1];
                    } else {
                        match[i][j] = false;
                    }
                }
            }
            
            return match[s.length()][p.length()];
        }
        
        public boolean checkEmpty(String p) {
            if (p.length() % 2 != 0) {
                return false;
            }
            for (int i = 1; i < p.length(); i+=2) {
                if (p.charAt(i) != '*') {
                    return false;
                }
            }
            return true;
        }
    }
    

Log in to reply
 

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