44.Wildcard Matching

Tags: [dp], [top_to_bottom_dp], [memo], [wildcard], [recursion]

Com: {fb}

Link: https://leetcode.com/problems/wildcard-matching/#/description

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).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

Solution: Recursion, Top To Bottom DP

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if s is None or p is None:
            raise ValueError('the input is invalid')

        memo = [[None for _ in xrange(len(p))] for _ in xrange(len(s))]
        return self.is_match_helper(s, 0, p, 0, memo)

    def is_match_helper(self, s, s_index, p, p_index, memo):
        # base case
        if p_index >= len(p):
            return s_index >= len(s)
        if s_index >= len(s):
            # check whether the remaining of p are all *.
            return all([p[i] == '*' for i in xrange(p_index, len(p))])

        if memo[s_index][p_index] is not None:
            return memo[s_index][p_index]

        curr_p = p[p_index]
        if curr_p != '*':
            result = self.single_match(s[s_index], p[p_index]) and\
                     self.is_match_helper(s, s_index + 1, p, p_index + 1, memo)
            memo[s_index][p_index] = result
            return result
        else:
            # curr_p == '*'
            # choice one: the current * match nothing
            # choice two: the current * match s[s_index]
            result = self.is_match_helper(s, s_index, p, p_index + 1, memo) or\
                     self.is_match_helper(s, s_index + 1, p, p_index, memo)
            memo[s_index][p_index] = result
            return result

    def single_match(self, sc, pc):
        return pc == '?' or pc == sc

Revelation:

• The reason we can use DP, because there is overlapping computation, the overlapping generated by the following code:

# curr_p == '*'
# choice one: the current * match nothing
# choice two: the current * match s[s_index]
result = self.is_match_helper(s, s_index, p, p_index + 1, memo) or\
         self.is_match_helper(s, s_index + 1, p, p_index, memo)

• Sometimes s__index, only increase p__index, sometimes, s__index increased, but p__index stop,

Note:

• Time complexity = O(len(s) * len(p)), because each cell of the memo, we only computed once.

Solution: Iteration

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if s is None or p is None:
            raise ValueError('the input is invalid')

        s_index = 0
        s_len = len(s)
        p_index = 0
        p_len = len(p)

        s_star_index = -1
        p_star_index = -1

        while s_index < s_len:
            if p_index >= p_len:
                if p_star_index < 0:
                    return False
                p_index = p_star_index
                s_index = s_star_index + 1
            else:
                sc = s[s_index]
                pc = p[p_index]

                if pc != '*':
                    if pc == '?' or pc == sc:
                        s_index += 1
                        p_index += 1
                    else:
                        if p_star_index < 0:
                            return False
                        else:
                            p_index = p_star_index
                            s_index = s_star_index + 1
                else:
                    # pc == '*'
                    p_star_index = p_index
                    s_star_index = s_index

                    p_index += 1

        if p_index < p_len:
            return all([p[i] == '*' for i in xrange(p_index, p_len)])

        return True

Revelation:

• Main while loop only check s_index < s_len, then if p gets to the end or sc and pc not match, we check whether there is p_star_index, if there is, we set p_index = p_star_index, and s_index = s_star_index + 1. And each time when we meet pc == '*', we try to make it match nothing, just keep s_index then p_index += 1, until we meet s and p mismatch, then we try to find back *.

Note:

• Time complexity = O(len(s) * len(p)), because each time when s and p mismatch, we will reset p_index to p_star_index and s_index to s_star_index + 1