Question

Formatted question description: https://leetcode.ca/all/44.html

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

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

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

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

Constraints:

0 <= s.length, p.length <= 2000
s contains only lowercase English letters.
p contains only lowercase English letters, '?' or '*'.

Algorithm

Note that this problem is different from another “Regular Expression Matching” question. The role of asterisks in the two questions is different. Pay attention to the differences between them.

The biggest difficulty in this problem is that the asterisk in the pattern can match any string, which makes it tricky to determine the corresponding position of the asterisk. Before the position of the asterisk, any character in the input string s can be matched with the asterisk. However, if there is a character in the pattern p that doesn’t exist in the input string s, the pattern cannot be matched because the asterisk can only add characters, not eliminate them. Therefore, once a character is missing, the pattern cannot be matched.

To solve this problem, two variables are used to represent the positions of the asterisk in the input string s and the pattern p. These positions are denoted by iStar and jStar, respectively, and are initialized to -1, which means that there is no asterisk by default. We also use two variables i and j to point to the current positions in the input string s and the pattern p, respectively.

To match the pattern with the input string, we start iterating through the input string s with a while loop, as long as i is less than the length of s.

If the current characters in s and p are equal, or if the character in p is a question mark, then we increment both i and j by 1.
If p[j] is an asterisk, we record the position of the asterisk by setting jStar to j, increment j by 1, and set iStar to i.
If p[j] is not an asterisk and cannot match s[i], we must use the asterisk at this point. If the asterisk has not appeared before, we return false immediately. If the asterisk has appeared before, we check the value of iStar to decide whether we can use the asterisk to continue matching.

Once all characters in s have been matched, we need to check the remaining pattern p. Only asterisks are allowed in the remaining pattern, and no other characters are allowed. If there are continuous asterisks in p, we filter them out. If j is not equal to the length of p, we return false.

Note

Wildcard Matching

Implement wildcard pattern matching with support for ‘?’ and ‘’. ‘?’ Matches any single character. ‘’ Matches any sequence of characters (including the empty sequence).

Regular Expression Matching

Implement regular expression matching with support for ‘.’ and ‘’. ‘.’ Matches any single character. ‘’ Matches zero or more of the preceding element.

The function prototypes for both topics are bool isMatch(const char *s, const char *p);

At first glance, these two questions thought they were the same, but they were not. The first question was actually wildcard matching, which means that the ‘’ sign can match any substring. The second question is actually regular expression matching, that is, the ‘’ sign means that the character before it can appear any number of times (including 0). This is actually the Klin closure described in the Long Book of Compilation Principles.

Code

public class Wildcard_Matching {

    public static void main(String[] args) {
        Wildcard_Matching out = new Wildcard_Matching();
        Solution_dp sdp = out.new Solution_dp();

        System.out.println(sdp.isMatch("", "*"));
        System.out.println(sdp.isMatch(null, "*"));
    }

    public class Solution_dp {

        public boolean isMatch(String s, String p) {

            if (s == null || p == null) {
                return false;
            }

            if (p.length() == 0) {
                return s.length() == 0;
            }

            // @note: need to comment out below, or else fail test case
            //          s="", p="******"
//            if (s.length() == 0) {
//                return p == "*"; // * matching emtpy string
//            }

            int m = s.length();
            int n = p.length();

            // dp[i][j]: up to i-th char in p, and up to j-th char in s, are matching.
            // note: i,j are not index
            boolean[][] dp = new boolean[m + 1][n + 1];
            dp[0][0] = true; // facilitate loop

            for (int i = 1; i <= n; ++i) {
                // if p starting with "*", then all true for dp[0][i]
                // or else, all false for dp[0][i]
                if (p.charAt(i - 1) == '*') dp[0][i] = dp[0][i - 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 - 1][j] || dp[i][j - 1];
                    } else {
                        dp[i][j] = (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?')
                            && dp[i - 1][j - 1];
                    }
                }
            }
            return dp[m][n];
        }
    }


    public class Solution_iteration {

        public boolean isMatch(String s, String p) {

            if (s == null || p == null) {
                return false;
            }

            if (p.length() == 0) {
                return s.length() == 0;
            }

            if (s.length() == 0) {
                return p == "*"; // * matching emtpy string
            }

            int i = 0;
            int j = 0;
            int iMark = -1;
            int jMark = -1;

            while (i < s.length()) {
                if (j < p.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')) {
                    i++;
                    j++;
                } else if (j < p.length() && p.charAt(j) == '*') {

                    // record i,j before trying different i positions
                    iMark = i;
                    jMark = j;

                    // skip * to match its next
                    j++;

                    //这一步是关键，匹配s中当前字符与p中‘＊’后面的字符，如果匹配，则在第一个if中处理，如果不匹配，则继续比较s中的下一个字符。
                } else if (jMark != -1) { // if reaching here, meaning one attempt of start at position iMkark failed, try another attempt

                    // another attempt, move iMark next, also move j to marked matching position
                    iMark++;
                    j = jMark + 1;

                    i = iMark;
                } else {
                    return false;
                }
            }

            // now scanned s, but possibly p is not fully scanned. Only remaining of p is all * then return true
            while (j < p.length() && p.charAt(j) == '*') {
                j++;
            }

            return j == p.length();

        }
    }


    public class Solution_over_time {
        /*
        test case, over time:

        "aaaabaaaabbbbaabbbaabbaababbabbaaaababaaabbbbbbaabbbabababbaaabaabaaaaaabbaabbbbaababbababaabbbaababbbba"
        "*****b*aba***babaa*bbaba***a*aaba*b*aa**a*b**ba***a*a*"

        */
        public boolean isMatch(String s, String p) {

            if (s == null || p == null) {
                return false;
            }

            if (p.length() == 0) {
                return s.length() == 0;
            }

            if (s.length() == 0) {
                return p == "*"; // * matching emtpy string
            }

            // now length of p and s are at least 1
            if (p.charAt(0) == '?') {
                return isMatch(s.substring(1), p.substring(1));
            } else if (p.charAt(0) == '*') {
                char prev = s.charAt(0);
                for (int i = 0; i < s.length(); i++) {
                    // when i=0, it's case: "b" matching "*b"
                    if (prev == s.charAt(i) && isMatch(s.substring(i + 1), p.substring(1))) { // @note: here i+1 for substring
                        return true;
                    }
                }
            } else { // normal cases
                return s.charAt(0) == p.charAt(0) && isMatch(s.substring(1), p.substring(1));
            }

            return false;
        }
    }
}

############

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 (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}

// OJ: https://leetcode.com/problems/wildcard-matching/
// Time: O(MN)
// Space: O(MN)
class Solution {
    int M, N;
    vector<vector<int>> m;
    bool isMatch(string &s, string &p, int i, int j) {
        if (m[i][j] != -1) return m[i][j];
        int &ans = m[i][j];
        for (; j < N; ++j) {
            if (p[j] != '*' && i >= M) return ans = false;
            if (p[j] == '?') ++i;
            else if (p[j] == '*') {
                while (j + 1 < N && p[j + 1] == '*') ++j;
                for (int k = 0; i + k <= M; ++k) {
                    if (isMatch(s, p, i + k, j + 1)) return ans = true;
                }
            } else if (s[i++] != p[j]) return ans = false;
        }
        return ans = i >= M;
    }
public:
    bool isMatch(string s, string p) {
        M = s.size(), N = p.size();
        m.assign(M + 1, vector<int>(N + 1, -1));
        return isMatch(s, p, 0, 0);
    }
};

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True

        # if p starting with "*", then all true for dp[0][i]
        # or else, all false for dp[0][i]
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 1]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s[i - 1] == p[j - 1] or p[j - 1] == '?':
                    dp[i][j] = dp[i - 1][j - 1]
                # dp[i - 1][j], where j is always '*', all the way back to i-1==0
                elif p[j - 1] == '*':
                    dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
        return dp[m][n]

############

class Solution(object):
  def isMatch(self, s, p):
    """
    :type s: str
    :type p: str
    :rtype: bool
    """
    i = j = 0
    lenS = len(s)
    lenP = len(p)
    lastMatchPos = 0
    lastStarPos = -1
    while i < len(s):
      if j < lenP and p[j] in (s[i], "?"):
        i += 1
        j += 1
      elif j < lenP and p[j] == "*":
        lastMatchPos = i
        lastStarPos = j
        j += 1
      elif lastStarPos > -1:
        i = lastMatchPos + 1
        lastMatchPos += 1
        j = lastStarPos + 1
      else:
        return False
    while j < lenP and p[j] == "*":
      j += 1
    return j == lenP

func isMatch(s string, p string) bool {
	m, n := len(s), len(p)
	dp := make([][]bool, m+1)
	for i := range dp {
		dp[i] = make([]bool, n+1)
	}
	dp[0][0] = true
	for j := 1; j <= n; j++ {
		if p[j-1] == '*' {
			dp[0][j] = dp[0][j-1]
		}
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if s[i-1] == p[j-1] || p[j-1] == '?' {
				dp[i][j] = dp[i-1][j-1]
			} else if p[j-1] == '*' {
				dp[i][j] = dp[i-1][j] || dp[i][j-1]
			}
		}
	}
	return dp[m][n]
}

using System.Linq;

public class Solution {
    public bool IsMatch(string s, string p) {
        if (p.Count(ch => ch != '*') > s.Length)
        {
            return false;
        }
        
        bool[,] f = new bool[s.Length + 1, p.Length + 1];
        bool[] d = new bool[s.Length + 1]; // d[i] means f[0, j] || f[1, j] || ... || f[i, j]
        for (var j = 0; j <= p.Length; ++j)
        {
            d[0] = j == 0 ? true : d[0] && p[j - 1] == '*';
            for (var i = 0; i <= s.Length; ++i)
            {
                if (j == 0)
                {
                    f[i, j] = i == 0;
                    continue;
                }
                
                if (p[j - 1] == '*')
                {
                    if (i > 0)
                    {
                        d[i] = f[i, j - 1] || d[i - 1];
                    }
                    f[i, j] = d[i];
                }
                else if (p[j - 1] == '?')
                {
                    f[i, j] = i > 0 && f[i - 1, j - 1];
                }
                else
                {
                    f[i, j] = i > 0 && f[i - 1, j - 1] && s[i - 1] == p[j - 1];
                }
            }
        }
        return f[s.Length, p.Length];
    }
}

44 - Wildcard Matching

Question

Algorithm

Note

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Note

Code

All Problems

All Solutions