This is the solution about Leetcode - 44.Wildcard Matching.

Description

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*’.

1
2
'?' 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:

1
2
3
4
5
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

1
2
3
4
5
Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

1
2
3
4
5
Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

1
2
3
4
5
Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Example 5:

1
2
3
4
Input:
s = "acdcb"
p = "a*c?b"
Output: false

Solution

Solution1

  1. Recursion: This solution is Time Limit Exceeded
  2. Each time we compare with the first letter of s and p. And recursively compare with the rest of s and p.
  3. if ‘*’ is present, it has three situations:
  4. star represents multiple letters -> compare s.substring(1) and p;
  5. star represents one letter -> compare s.substring(1) and p.substring(1);
  6. star represents none letter -> compare s and p.substring(1);

Solution2

  1. DP solution.
  2. Record first i and first j letters of s and p are matched or not into array. From (0,0) to (s.length(), p.length()) to get the result of s and p.
  3. Similar thinking of recursive solution. if ‘*’ is present, it has three situations:
  4. ‘*’ represents multiple letters -> j should match i-1 as well -> dp[i+1][j+1] = dp[i][j+1]
  5. ‘*’ represents one letter -> i-1 and j-1 are matched -> dp[i+1][j+1] = dp[i][j]
  6. ‘*’ represents none letter -> i and j-1 are matched -> dp[i+1][j+1] = dp[i+1][j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Solution1 {
public boolean isMatch(String s, String p) {
//check the termination
if(p.length() == 0) return s.length() == 0;
//corner case: "" "***"
if(s.length() == 0) return p.charAt(0)=='*' && isMatch(s, p.substring(1));
if(s.charAt(0)==p.charAt(0) || p.charAt(0)=='?') {
return isMatch(s.substring(1), p.substring(1));
}else if(p.charAt(0) == '*') {
return isMatch(s.substring(1), p) || isMatch(s.substring(1), p.substring(1)) || isMatch(s,p.substring(1));
}
return false;
}
}
public class Solution2 {
public boolean isMatch(String s, String p) {
//state: matches[i][j] represents first i characters of s and first j characters of p are matched or not
boolean[][] matches = new boolean[s.length()+1][p.length()+1];
//init:first 0 characters of s and first 0 characters of p must be matched
matches[0][0] = true;
//init matches[0][j]
for(int j = 0; j < p.length(); j++) {
if(p.charAt(j) == '*' && matches[0][j]) matches[0][j+1] = true;
}
//init matches[i][0], always false
//function
for(int i = 0; i < s.length(); i++) {
for(int j = 0; j < p.length(); j++) {
if(s.charAt(i)==p.charAt(j) || p.charAt(j)=='?') {
matches[i+1][j+1] = matches[i][j];
}else if (p.charAt(j) == '*') {
//* represents none -> i and j-1 are matched
//* represents one character -> i-1 and j-1 are matched
//* represents multiple characters -> i-1 and j are matched
matches[i+1][j+1] = matches[i+1][j] || matches[i][j] || matches[i][j+1];
}
}
}
//answer
return matches[s.length()][p.length()];
}
}