44 Wildcard Matching

44. Wildcard Matching

1. Question

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

2. Implementation

(1) Two Pointers

class Solution {
    public boolean isMatch(String s, String p) {
        int sIndex = 0, pIndex = 0;
        int matchIndex = -1, starIndex = -1;

        while (sIndex < s.length()) {
            // case 1: p.charAt(pIndex) == s.charAt(sIndex) 或者 p.charAt(pIndex) == ?时， pIndex所在的位置匹配sIndex的字符
            // 同时移动pIndex和sIndex
            if (pIndex < p.length() && (p.charAt(pIndex) == s.charAt(sIndex) || p.charAt(pIndex) == '?')) {
                ++pIndex;
                ++sIndex;
            }
            // case 2: 如果p.charAt(pIndex)为*， 此时的*可能不匹配任何s的子串，所以保留starIndex，之后可能会用到，并且我们先不移动sIndex
            // (因为*可能不匹配任何s的子串), 并
            else if (pIndex < p.length() && p.charAt(pIndex) == '*') {
                starIndex = pIndex;
                ++pIndex;
                // 此时的 sIndex 还不确定是否要被 * 表示，需要继续从sIndex开始遍历，如果后面某个位置发生匹配错误，
                // 则表示sIndex应该被*表示，重新回复从 sIndex+1 开始重新匹配
                matchIndex = sIndex;
            }
            // case 3: 匹配失败，说明matchIndex指向的字符应该被*表示，回溯到matchIndex+1，重新开始进行 starIndex+1和matchIndex+1匹配
            else if (starIndex > -1) {
                pIndex = starIndex + 1;
                sIndex = matchIndex + 1;
                ++matchIndex;
            }
            else {
                return false;
            }
        }

        //s已经遍历完，p按理最多只剩下*，如果还存在非*字母，则匹配失败
        while (pIndex < p.length() && p.charAt(pIndex) == '*') {
            ++pIndex;
        }
        return pIndex == p.length();
    }
}

(2) DP

解析

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];

        dp[0][0] = true;

        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 1];
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                }
                else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else {
                    dp[i][j] = false;
                }
            }
        }
        return dp[m][n];
    }
}

3. Time & Space Complexity

Two Pointers: 时间复杂度O(mn), 空间复杂度O(1)

DP: 时间复杂度O(mn), 空间复杂度O(mn)