Wild Card Matching & Regular Expression Matching, let's put em together


  • 1

    Actually the DP solution of these two question are quite similar. It's more like reverse the strings and we can get a same solution for one question from another.

    Below some different solutions for these two questions.

    First, the DP solution. - 44. Wildcard Matching

    public class Solution {
        public boolean isMatch(String s, String p) {
            int slen = s.length(), plen = p.length();
            boolean[][] dp = new boolean[slen + 1][plen + 1];
            dp[slen][plen] = true;
            for (int j = plen - 1; j >= 0; j--) {
                dp[slen][j] = p.charAt(j) == '*' && dp[slen][j + 1];
            }
            
            /*
                if p.charAt(j) == '*', dp[i][j] = true, if:
                    1. match zero element, dp[i][j + 1];
                    2. match at least one element, dp[i + 1][j]
            */
            for (int i = slen - 1; i >= 0; i--) {
                for (int j = plen - 1; j >= 0; j--) {
                    if (p.charAt(j) != '*') {
                        dp[i][j] = dp[i + 1][j + 1] && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?');
                    } else {
                        dp[i][j] = dp[i][j + 1] || dp[i + 1][j];
                    }
                }
            }
            return dp[0][0];
        }
    }
    

    And the DP solution for 10. Regular Expression Matching.

    public class Solution {
        public boolean isMatch(String s, String p) {
            int slen = s.length(), plen = p.length();
            boolean[][] dp = new boolean[slen + 1][plen + 1];
            dp[0][0] = true;
            // matches the empty string
            for (int j = 1; j <= plen; j++) {
                dp[0][j] = j > 1 && dp[0][j - 2] && p.charAt(j - 1) == '*';
            }
            /* When p[j - 1] == '*', dp[i][j] = true
                if:
                1. match zero element, dp[i][j - 2]
                2 . match at least one element, dp[i - 1][j] && s[i - 1] matches p[j - 2]
            */
            for (int i = 1; i <= slen; i++) {
                for (int j = 1; j <= plen; j++) {
                    if (p.charAt(j - 1) != '*') {
                        dp[i][j] = dp[i - 1][j - 1] && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.');
                    } else {
                        dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.'));
                    }
                }
            }
            return dp[slen][plen];
        }
    }
    

    Besides, this is the recursion solution for 10. Regular Expression Matching, from here.

    public class Solution {
        public boolean isMatch(String s, String p) {
            if (p.length() == 0) return s.length() == 0;
            if (p.length() == 1) return s.length() == 1 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
            if (p.charAt(1) == '*') {
                return isMatch(s, p.substring(2)) || (s.length() > 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')) && isMatch(s.substring(1), p);
            } else {
                if (s.length() == 0) return false;
                return (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') ? isMatch(s.substring(1), p.substring(1)) : false;
            }
        }
    }
    

    And this is the greedy algorithm for 44. Wildcard Matching, from here.

    public class Solution {
        public boolean isMatch(String s, String p) {
            int i = 0, j = 0, match = 0, star = -1;
            while (i < s.length()) {
                if (j < p.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
                    i++;
                    j++;
                    continue;
                }
                if (j < p.length() && p.charAt(j) == '*') {
                    match = i;
                    star = j++;
                    continue;
                }
                if (star >= 0) {
                    i = ++match;
                    j = star + 1;
                    continue;
                }
                return false;
            }
            while (j < p.length()) {
                if (p.charAt(j++) != '*') return false;
            }
            return true;
        }
    }
    

Log in to reply
 

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