44.Wildcard-Matching
44. Wildcard Matching
题目地址
https://leetcode.com/problems/wildcard-matching/
https://blog.csdn.net/jmspan/article/details/51460021
题目描述
Given an input string (s) and a pattern (p), 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).
Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like ? or *.
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代码
Approach 1: DFS
class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null) return false;
if (s.length() == 0 || p.length() == 0) return false;
return dfs(s, 0, p, 0);
}
private boolean dfs(String s, int sIdx, String p, int pIdx) {
if (sIdx == s.length() || pIdx == p.length()) {
if (sIdx == s.length() && pIdx == p.length()) {
return true;
} else {
return false;
}
}
if (p.charAt(pIdx) == '*') {
// remove continuous *
while (p.charAt(pIdx) == '*')
pIdx++;
if (pIdx == p.length()) return true;
}
// compare remaining part of p after * with s
while (sIdx < s.length() && !dfs(s, sIdx, p, pIdx)) {
sIdx++;
}
// sIdx 不能为空
return sIdx != s.length();
} else if (s.charAt(sIdx) == p.chaAt(pIdx) || p.charAt(pIdx) == '?') {
return dfs(s, sIdx + 1, p, pIdx + 1);
} else {
return false;
}
}
}Approach #2 Dynamic Programming
Time complexity : O(SP) && Space complexity : O(SP) to keep the matrix.
class Solution {
public boolean isMatch(String s, String p) {
int sLen = s.length(), pLen = p.length();
// base cases
if (p.equals(s) || p.equals("*")) return true;
if (p.isEmpty() || s.isEmpty()) return false;
// init all matrix except [0][0] element as False
boolean[][] d = new boolean[pLen + 1][sLen + 1];
d[0][0] = true;
// DP compute
for (int pIdx = 1; pIdx < pLen + 1; pIdx++) {
// the current character in the pattern is '*'
if (p.charAt(pIdx - 1) == '*') {
int sIdx = 1;
// d[p_idx - 1][s_idx - 1] is a string-pattern match
// on the previous step, i.e. one character before.
// Find the first idx in string with the previous math.
while ((!d[pIdx - 1][sIdx - 1]) && (sIdx < sLen + 1)) sIdx++;
// If (string) matches (pattern),
// when (string) matches (pattern)* as well
d[pIdx][sIdx - 1] = d[pIdx - 1][sIdx - 1];
// If (string) matches (pattern),
// when (string)(whatever_characters) matches (pattern)* as well
while (sIdx < sLen + 1) d[pIdx][sIdx++] = true;
}
// the current character in the pattern is '?'
else if (p.charAt(pIdx - 1) == '?') {
for (int sIdx = 1; sIdx < sLen + 1; sIdx++)
d[pIdx][sIdx] = d[pIdx - 1][sIdx - 1];
}
// the current character in the pattern is not '*' or '?'
else {
for (int sIdx = 1; sIdx < sLen + 1; sIdx++) {
// Match is possible if there is a previous match
// and current characters are the same
d[pIdx][sIdx] = d[pIdx - 1][sIdx - 1] &&
(p.charAt(pIdx - 1) == s.charAt(sIdx - 1));
}
}
}
return d[pLen][sLen];
}
}Approach #3 Dynamic Programming - 2
boolean strmatch(String str, String pattern, int n, int m) {
// empty pattern can only match with
// empty string
if (m == 0)
return (n == 0);
// lookup table for storing results of
// subproblems
boolean[][] lookup = new boolean[n + 1][m + 1];
// initailze lookup table to false
for(int i = 0; i < n + 1; i++)
Arrays.fill(lookup[i], false);
// empty pattern can match with empty string
lookup[0][0] = true;
// Only '*' can match with empty string
for (int j = 1; j <= m; j++)
if (pattern.charAt(j - 1) == '*')
lookup[0][j] = lookup[0][j - 1];
// fill the table in bottom-up fashion
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
// Two cases if we see a '*'
// a) We ignore '*'' character and move
// to next character in the pattern,
// i.e., '*' indicates an empty sequence.
// b) '*' character matches with ith
// character in input
if (pattern.charAt(j - 1) == '*')
lookup[i][j] = lookup[i][j - 1] ||
lookup[i - 1][j];
// Current characters are considered as
// matching in two cases
// (a) current character of pattern is '?'
// (b) characters actually match
else if (pattern.charAt(j - 1) == '?' ||
str.charAt(i - 1) == pattern.charAt(j - 1))
lookup[i][j] = lookup[i - 1][j - 1];
// If characters don't match
else lookup[i][j] = false;
}
}
return lookup[n][m];
}Approach #3 Backtracking
Time complexity : O(min(S,P)) && Space complexity : O(1)
class Solution {
public boolean isMatch(String s, String p) {
int sLen = s.length(), pLen = p.length();
int sIdx = 0, pIdx = 0;
int starIdx = -1, sTmpIdx = -1;
while (sIdx < sLen) {
// If the pattern caracter = string character
// or pattern character = '?'
if (pIdx < pLen && (p.charAt(pIdx) == '?' || p.charAt(pIdx) == s.charAt(sIdx))){
++sIdx;
++pIdx;
}
// If pattern character = '*'
else if (pIdx < pLen && p.charAt(pIdx) == '*') {
// Check the situation
// when '*' matches no characters
starIdx = pIdx;
sTmpIdx = sIdx;
++pIdx;
}
// If pattern character != string character
// or pattern is used up
// and there was no '*' character in pattern
else if (starIdx == -1) {
return false;
}
// If pattern character != string character
// or pattern is used up
// and there was '*' character in pattern before
else {
// Backtrack: check the situation
// when '*' matches one more character
pIdx = starIdx + 1;
sIdx = sTmpIdx + 1;
sTmpIdx = sIdx;
}
}
// The remaining characters in the pattern should all be '*' characters
for (int i = pIdx; i < pLen; i++)
if (p.charAt(i) != '*') return false;
return true;
}
}Last updated