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).
Examples:
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'.Solution in Python:
To solve the wildcard pattern matching problem where the pattern can include ? and *, we can use dynamic programming.
Python
class Solution:
def isMatch(self, s: str, p: str) -> bool:
# Initialize the DP table with False
dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
# Base case: empty pattern matches empty string
dp[0][0] = True
# Handle patterns like *, **, ***, etc.
for j in range(1, len(p) + 1):
if p[j - 1] == '*':
dp[0][j] = dp[0][j - 1]
# Fill the DP table
for i in range(1, len(s) + 1):
for j in range(1, len(p) + 1):
if p[j - 1] == s[i - 1] or p[j - 1] == '?':
# If characters match or pattern character is '?'
dp[i][j] = dp[i - 1][j - 1]
elif p[j - 1] == '*':
# If pattern character is '*', it can match any sequence
dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
return dp[len(s)][len(p)]Detailed Explanation:
- Initialization:
- We use a 2D list
dpwheredp[i][j]will beTrueif the firsticharacters in the stringsmatch the firstjcharacters of the patternp. - The size of
dpis(len(s) + 1) x (len(p) + 1)because we need to account for the empty string and empty pattern.
- We use a 2D list
- Base Case:
dp[0][0]isTruebecause an empty pattern matches an empty string.- We also handle the case where the pattern starts with one or more
*. Each*can match the empty sequence, so we propagateTruefrom left to right in the first row of the DP table.
- Filling the DP Table:
- We iterate through each character of the string
sand the patternp. - If the characters match (
s[i - 1] == p[j - 1]) or if the pattern has a?, we setdp[i][j] = dp[i - 1][j - 1]. - If the pattern has a
*, it can either match zero characters (dp[i][j - 1]) or match one or more characters (dp[i - 1][j]).
- We iterate through each character of the string
- Final Result:
- The final result is in
dp[len(s)][len(p)], which indicates whether the entire string matches the entire pattern.
- The final result is in
This approach ensures that we efficiently handle the wildcard pattern matching problem within the constraints given.
Solution in Javascript:
JavaScript
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
// Initialize the DP table with false
let dp = Array.from({ length: s.length + 1 }, () => Array(p.length + 1).fill(false));
// Base case: empty pattern matches empty string
dp[0][0] = true;
// Handle patterns like *, **, ***, etc.
for (let j = 1; j <= p.length; j++) {
if (p[j - 1] === '*') {
dp[0][j] = dp[0][j - 1];
}
}
// Fill the DP table
for (let i = 1; i <= s.length; i++) {
for (let j = 1; j <= p.length; j++) {
if (p[j - 1] === s[i - 1] || p[j - 1] === '?') {
// If characters match or pattern character is '?'
dp[i][j] = dp[i - 1][j - 1];
} else if (p[j - 1] === '*') {
// If pattern character is '*', it can match any sequence
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
}
}
}
return dp[s.length][p.length];
};Solution in Java:
Java
class Solution {
public boolean isMatch(String s, String p) {
// Initialize the DP table with false
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
// Base case: empty pattern matches empty string
dp[0][0] = true;
// Handle patterns like *, **, ***, etc.
for (int j = 1; j <= p.length(); j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 1];
}
}
// Fill the DP table
for (int i = 1; i <= s.length(); i++) {
for (int j = 1; j <= p.length(); j++) {
if (p.charAt(j - 1) == s.charAt(i - 1) || p.charAt(j - 1) == '?') {
// If characters match or pattern character is '?'
dp[i][j] = dp[i - 1][j - 1];
} else if (p.charAt(j - 1) == '*') {
// If pattern character is '*', it can match any sequence
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
}
}
}
return dp[s.length()][p.length()];
}
}Solution in C#:
C#
public class Solution {
public bool IsMatch(string s, string p) {
// Initialize the DP table with false
bool[,] dp = new bool[s.Length + 1, p.Length + 1];
// Base case: empty pattern matches empty string
dp[0, 0] = true;
// Handle patterns like *, **, ***, etc.
for (int j = 1; j <= p.Length; j++) {
if (p[j - 1] == '*') {
dp[0, j] = dp[0, j - 1];
}
}
// Fill the DP table
for (int i = 1; i <= s.Length; i++) {
for (int j = 1; j <= p.Length; j++) {
if (p[j - 1] == s[i - 1] || p[j - 1] == '?') {
// If characters match or pattern character is '?'
dp[i, j] = dp[i - 1, j - 1];
} else if (p[j - 1] == '*') {
// If pattern character is '*', it can match any sequence
dp[i, j] = dp[i - 1, j] || dp[i, j - 1];
}
}
}
return dp[s.Length, p.Length];
}
}