# 0044. Wildcard Matching ## Description 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'. ``` **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 ``` **Constraints:** * `0 <= s.length, p.length <= 2000` * `s` contains only lowercase English letters. * `p` contains only lowercase English letters, `'?'` or `'*'`. ## ac1: 2D dp similar with #10 ```java class Solution { public boolean isMatch(String s, String p) { // edge cases if (s == null || p == null) return false; // initialize boolean[][] dp = new boolean[s.length()+1][p.length()+1]; dp[0][0] = true; for (int i = 1; i < dp[0].length; i++) { // s is empty, p has to be all "*" to be true. if (p.charAt(i-1) == '*') { dp[0][i] = true; } else { break; } } // walk, function transformation for (int i = 1; i < dp.length; i++) { for (int j = 1; j < dp[0].length; j++) { if (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j-1) == '?') { dp[i][j] = dp[i-1][j-1]; } if (p.charAt(j-1) == '*') { dp[i][j] = dp[i][j-1] || dp[i-1][j]; } } } // result return dp[s.length()][p.length()]; } } /* state: dp[i][j], s.substring(0, i) and p.substring(0, j) is match function: 1. if p.charAt(j-1) == s.charAt(i-1) , dp[i][j] = dp[i-1][j-1]; 2. if p.charAt(j-1) == '?' , dp[i][j] = dp[i-1][j-1]; 3. if p.charAt(j-1) == '*' : (1) * means empty: dp[i][j] = dp[i][j-1]; (2) * means anything: dp[i][j] = dp[i-1][j]; initialize: dp[0][0] = true; dp[0][i] result: dp[s.length()][p.length()] */ ``` ### ac2: 1D DP Notice: 1D dp, need to update each one in the array, because it does not have default value, unlike 2D dp. `else dp[j] = false;` ```java class Solution { public boolean isMatch(String s, String p) { // edge cases if (s == null || p == null) return false; // initialize boolean[] dp = new boolean[p.length()+1]; dp[0] = true; for (int i = 1; i < dp.length; i++) { if (p.charAt(i-1) == '*') { dp[i] = true; } else { break; } } // walk, function transformation for (int i = 1; i <= s.length(); i++) { boolean prev = dp[0]; dp[0] = false; for (int j = 1; j < dp.length; j++) { boolean tmp = dp[j]; if (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j-1) == '?') { dp[j] = prev; } else if (p.charAt(j-1) == '*') { dp[j] = dp[j-1] || dp[j]; } else { dp[j] = false; } prev = tmp; } } // result return dp[p.length()]; } } ``` ### ac3: 2 pointers ```java class Solution { public boolean isMatch(String s, String p) { // edge cases if (s == null || p == null) return false; // 2 pointers, walk int si = 0, pi = 0, starIndex = -1, sRestart = 0; while (si < s.length()) { if (pi < p.length() && (s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '?') ) { si++; pi++; } else if (pi < p.length() && p.charAt(pi) == '*') { starIndex = pi; sRestart = si; pi++; } // s.charAt(si) != p.charAt(pi) else if (starIndex != -1) { // meet * before, let * kill one char in s sRestart++; si = sRestart; pi = starIndex + 1; } else { return false; } } // check pattern remaining while (pi < p.length() && p.charAt(pi) == '*') { pi++; } // if match, pi should hit the end of pattern return pi == p.length(); } } /* 2 pointers si, pi if s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '?' , move on, si++; pi++; if p.charAt(pi) == '*': meet * , starI = pi, sRestart = si(in case * will offset chars in s), pi++ if s.charAt(si) != p.charAt(pi): 1) have * before starI != -1 : '*' can kill char in s one by one sRestart++; si = sRestart; (the * offset one char in s) pi = starI + 1; 2) don't have *, return false; abededab ?b*d** a=?, go on, b=b, go on, e=*, save * position star=3, save s position ss = 3, p++ e!=d, check if there was a *, yes, ss++, s=ss; p=star+1 // the * offset 'e' d=d, go on, meet the end. check the rest element in p, if all are *, true, else false; */ ``` ## Similar problems * [010-Regular Expression Matching](https://github.com/jaywinhuang/leetcode/blob/master/solutions/010-regular-expression-matching.md) --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://jaywin.gitbook.io/leetcode/solutions/0044-wildcard-matching.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.