Given two strings pattern and str which may be of different size, You have to return 1 if the wildcard pattern i.e. pattern, matches with str else return 0. All characters of the string str and pattern always belong to the Alphanumeric characters.
The wildcard pattern can include the characters ? and *
‘?’ – matches any single character.
‘*’ – Matches any sequence of characters (including the empty sequence).
Note: The matching should cover the entire str (not partial str).
Examples:
Input: pattern = "ba*a?", str = "baaabab" Output: 1 Explanation: replace '*' with "aab" and '?' with 'b'.
Input: pattern = "a*ab", str = "baaabab" Output: 0 Explanation: Because in string pattern character 'a' at first position, pattern and str can't be matched.
Expected Time Complexity: O(n*m)
Expected Auxiliary Space: O(n*m)
Constraints:
1 <= length of(str, pattern) <= 200
Approach 01:
-
C++
-
Python
class Solution {
public:
int checkPatternMatch(string& pattern, string& text, vector<vector<int>>& memo, int textIndex, int patternIndex) {
if (textIndex < 0 && patternIndex < 0) {
return 1;
}
if (textIndex >= 0 && patternIndex < 0) {
return 0;
}
if (textIndex < 0 && patternIndex >= 0) {
for (int k = patternIndex; k >= 0; k--) {
if (pattern[k] != '*') {
return 0;
}
}
return 1;
}
if (memo[textIndex][patternIndex] != -1) {
return memo[textIndex][patternIndex];
}
if (text[textIndex] == pattern[patternIndex] || pattern[patternIndex] == '?') {
return memo[textIndex][patternIndex] = checkPatternMatch(pattern, text, memo, textIndex - 1, patternIndex - 1);
} else {
if (pattern[patternIndex] == '*') {
return memo[textIndex][patternIndex] = checkPatternMatch(pattern, text, memo, textIndex - 1, patternIndex) || checkPatternMatch(pattern, text, memo, textIndex, patternIndex - 1);
} else {
return memo[textIndex][patternIndex] = 0;
}
}
}
int wildCard(string pattern, string text) {
int textLength = text.length();
int patternLength = pattern.length();
vector<vector<int>> memo(textLength + 1, vector<int>(patternLength + 1, -1));
return checkPatternMatch(pattern, text, memo, textLength - 1, patternLength - 1);
}
};
class Solution:
def checkPatternMatch(self, pattern, text, memo, textIndex, patternIndex):
if textIndex < 0 and patternIndex < 0:
return 1
if textIndex >= 0 and patternIndex < 0:
return 0
if textIndex < 0 and patternIndex >= 0:
for k in range(patternIndex, -1, -1):
if pattern[k] != '*':
return 0
return 1
if memo[textIndex][patternIndex] != -1:
return memo[textIndex][patternIndex]
if text[textIndex] == pattern[patternIndex] or pattern[patternIndex] == '?':
memo[textIndex][patternIndex] = self.checkPatternMatch(pattern, text, memo, textIndex - 1, patternIndex - 1)
else:
if pattern[patternIndex] == '*':
memo[textIndex][patternIndex] = self.checkPatternMatch(pattern, text, memo, textIndex - 1, patternIndex) or self.checkPatternMatch(pattern, text, memo, textIndex, patternIndex - 1)
else:
memo[textIndex][patternIndex] = 0
return memo[textIndex][patternIndex]
def wildCard(self, pattern, text):
textLength = len(text)
patternLength = len(pattern)
memo = [[-1 for _ in range(patternLength + 1)] for _ in range(textLength + 1)]
return self.checkPatternMatch(pattern, text, memo, textLength - 1, patternLength - 1)
Time Complexity
- Traversal:
The function traverses each node of the binary tree exactly once. Since there are \( n \) nodes in the tree, the time complexity is \( O(n) \).
Space Complexity
- Recursive Call Stack:
In the worst case (for a skewed tree), the depth of the recursion stack can go up to \( O(n) \). For a balanced tree, the depth of the recursion stack would be \( O(\log n) \).
- Result Vector:
The result vector stores the values of all nodes, requiring \( O(n) \) space.
- Overall Space Complexity:
The overall space complexity is \( O(n) \), considering the worst-case space usage of the recursion stack and the result vector.