44. Wildcard Matching

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Note:

• s could be empty and contains only lowercase letters a-z .
• p could be empty and contains only lowercase letters a-z , and characters like ? or * .

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:

s = "aa"
p = "*"

Output:
 true

Explanation:
 '*' matches any sequence.

Example 3:

Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

Input:

s = "adceb"
p = "*a*b"

Output:
 true

Explanation:
 The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Example 5:

Input:
s = "acdcb"
p = "a*c?b"
Output: false

Solution

(1) Java

class Solution {
    public boolean isMatch(String s, String p) {
        int slen = s.length();
        int plen = p.length();
        if (slen == 0 && plen == 0) {
            return true;
        } 
        boolean[][] dp = new boolean[slen+1][plen+1];
        dp[0][0] = true;
        for (int i = 0; i < plen; i++) {
            if (p.charAt(i) == '*') {
                dp[0][i+1] = true;
            } else {
                break;
            }
        }
        for (int i = 1; i <= slen; i++) {
            for (int j = 1; j <= plen; j++) {
                char sc = s.charAt(i-1);
                char pc = p.charAt(j-1);
                if (sc == pc || pc == '?') {
                    dp[i][j] = dp[i-1][j-1];
                } else if (pc == '*') {
                    dp[i][j] = dp[i-1][j]|dp[i][j-1];
                }
            }
        }
        return dp[slen][plen];
    }
}

Recursive version

class Solution {
    public boolean isMatch(String s, String p) {
        int[][] mem = new int[s.length()+1][p.length()+1];
        return helper(s, p, 0, 0, mem);
    }

    private boolean helper(String s, String p, int si, int pi, int[][] mem) {
        String key = Integer.toString(si) + "-" + Integer.toString(pi);
        if (mem[si][pi] != 0) {
            return mem[si][pi] == 1 ? true : false;
        }
        if (si == s.length() && pi == p.length()) {
            mem[si][pi] = 1;
            return true;
        } else if (pi == p.length()) {
            mem[si][pi] = -1;
            return false;
        } else if (si == s.length()) {
            for (int i = pi; i < p.length(); i++) {
                if (p.charAt(i) != '*') {
                    mem[si][pi] = -1;
                    return false;
                }
            }
            mem[si][pi] = 1;
            return true;
        }

        boolean rst = false;
        if (s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '?') {
            rst = helper(s, p, si+1, pi+1, mem);
        } else if (p.charAt(pi) == '*') {
            rst = helper(s, p, si+1, pi, mem) || helper(s, p, si, pi+1, mem);
        }
        mem[si][pi] = rst == true ? 1 : -1;
        return rst;
    }
}

(2) Python

class Solution:
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """

        def helper(i, j):
            if i == len(s) and j == len(p):
                return True
            elif j == len(p):
                return False
            elif i == len(s):
                for c in p[j:]:
                    if c != '*':
                        return False
                return True
            key = str(i)+"-"+str(j)
            rst = False
            if key in mem:
                return mem[key]
            if s[i] == p[j] or p[j] == '?':
                rst = helper(i+1, j+1)
            elif p[j] == '*':
                rst = helper(i, j+1) or helper(i+1, j)
            mem[key] = rst
            return rst
        mem = {}
        return helper(0, 0)

(3) Scala