Greedy
Recursion
String
Dynamic Programming
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'.
Constraints:
0 <= s.length, p.length <= 2000
s
contains only lowercase English letters.
p
contains only lowercase English letters, '?'
or '*'
.
Solutions
Solution 1: Memoization Search
We design a function $dfs(i, j)$, which represents whether the string $s$ starting from the $i$-th character matches the string $p$ starting from the $j$-th character. The answer is $dfs(0, 0)$.
The execution process of the function $dfs(i, j)$ is as follows:
If $i \geq \textit{len}(s)$, then $dfs(i, j)$ is true only when $j \geq \textit{len}(p)$ or $p[j] = '*'$ and $dfs(i, j + 1)$ is true.
If $j \geq \textit{len}(p)$, then $dfs(i, j)$ is false.
If $p[j] = '*'$, then $dfs(i, j)$ is true if and only if $dfs(i + 1, j)$ or $dfs(i + 1, j + 1)$ or $dfs(i, j + 1)$ is true.
Otherwise, $dfs(i, j)$ is true if and only if $p[j] = '?'$ or $s[i] = p[j]$ and $dfs(i + 1, j + 1)$ is true.
To avoid repeated calculations, we use the method of memoization search and store the result of $dfs(i, j)$ in a hash table.
The time complexity is $O(m \times n)$, and the space complexity is $O(m \times n)$. Where $m$ and $n$ are the lengths of the strings $s$ and $p$, respectively.
Python3 Java C++ Go TypeScript C#
1
2
3
4
5
6
7
8
9
10
11
12
13 class Solution :
def isMatch ( self , s : str , p : str ) -> bool :
@cache
def dfs ( i : int , j : int ) -> bool :
if i >= len ( s ):
return j >= len ( p ) or ( p [ j ] == "*" and dfs ( i , j + 1 ))
if j >= len ( p ):
return False
if p [ j ] == "*" :
return dfs ( i + 1 , j ) or dfs ( i + 1 , j + 1 ) or dfs ( i , j + 1 )
return ( p [ j ] == "?" or s [ i ] == p [ j ]) and dfs ( i + 1 , j + 1 )
return dfs ( 0 , 0 )
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 class Solution {
private Boolean [][] f ;
private char [] s ;
private char [] p ;
private int m ;
private int n ;
public boolean isMatch ( String s , String p ) {
this . s = s . toCharArray ();
this . p = p . toCharArray ();
m = s . length ();
n = p . length ();
f = new Boolean [ m ][ n ] ;
return dfs ( 0 , 0 );
}
private boolean dfs ( int i , int j ) {
if ( i >= m ) {
return j >= n || ( p [ j ] == '*' && dfs ( i , j + 1 ));
}
if ( j >= n ) {
return false ;
}
if ( f [ i ][ j ] != null ) {
return f [ i ][ j ] ;
}
if ( p [ j ] == '*' ) {
f [ i ][ j ] = dfs ( i + 1 , j ) || dfs ( i + 1 , j + 1 ) || dfs ( i , j + 1 );
} else {
f [ i ][ j ] = ( p [ j ] == '?' || s [ i ] == p [ j ] ) && dfs ( i + 1 , j + 1 );
}
return f [ i ][ 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 class Solution {
public :
bool isMatch ( string s , string p ) {
int m = s . size (), n = p . size ();
int f [ m + 1 ][ n + 1 ];
memset ( f , -1 , sizeof ( f ));
function < bool ( int , int ) > dfs = [ & ]( int i , int j ) {
if ( i >= m ) {
return j >= n || ( p [ j ] == '*' && dfs ( i , j + 1 ));
}
if ( j >= n ) {
return false ;
}
if ( f [ i ][ j ] != -1 ) {
return f [ i ][ j ] == 1 ;
}
if ( p [ j ] == '*' ) {
f [ i ][ j ] = dfs ( i + 1 , j ) || dfs ( i , j + 1 ) ? 1 : 0 ;
} else {
f [ i ][ j ] = ( p [ j ] == '?' || s [ i ] == p [ j ]) && dfs ( i + 1 , j + 1 ) ? 1 : 0 ;
}
return f [ i ][ j ] == 1 ;
};
return dfs ( 0 , 0 );
}
};
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 func isMatch ( s string , p string ) bool {
m , n := len ( s ), len ( p )
f := make ([][] int , m + 1 )
for i := range f {
f [ i ] = make ([] int , n + 1 )
}
var dfs func ( i , j int ) bool
dfs = func ( i , j int ) bool {
if i >= m {
return j >= n || p [ j ] == '*' && dfs ( i , j + 1 )
}
if j >= n {
return false
}
if f [ i ][ j ] != 0 {
return f [ i ][ j ] == 1
}
f [ i ][ j ] = 2
ok := false
if p [ j ] == '*' {
ok = dfs ( i + 1 , j ) || dfs ( i + 1 , j + 1 ) || dfs ( i , j + 1 )
} else {
ok = ( p [ j ] == '?' || s [ i ] == p [ j ]) && dfs ( i + 1 , j + 1 )
}
if ok {
f [ i ][ j ] = 1
}
return ok
}
return dfs ( 0 , 0 )
}
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 function isMatch ( s : string , p : string ) : boolean {
const m = s . length ;
const n = p . length ;
const f : number [][] = Array . from ({ length : m + 1 }, () =>
Array . from ({ length : n + 1 }, () => - 1 ),
);
const dfs = ( i : number , j : number ) : boolean => {
if ( i >= m ) {
return j >= n || ( p [ j ] === '*' && dfs ( i , j + 1 ));
}
if ( j >= n ) {
return false ;
}
if ( f [ i ][ j ] !== - 1 ) {
return f [ i ][ j ] === 1 ;
}
if ( p [ j ] === '*' ) {
f [ i ][ j ] = dfs ( i + 1 , j ) || dfs ( i , j + 1 ) ? 1 : 0 ;
} else {
f [ i ][ j ] = ( p [ j ] === '?' || s [ i ] === p [ j ]) && dfs ( i + 1 , j + 1 ) ? 1 : 0 ;
}
return f [ i ][ j ] === 1 ;
};
return dfs ( 0 , 0 );
}
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 public class Solution {
private bool? [,] f ;
private char [] s ;
private char [] p ;
private int m ;
private int n ;
public bool IsMatch ( string s , string p ) {
this . s = s . ToCharArray ();
this . p = p . ToCharArray ();
m = s . Length ;
n = p . Length ;
f = new bool? [ m , n ];
return Dfs ( 0 , 0 );
}
private bool Dfs ( int i , int j ) {
if ( i >= m ) {
return j >= n || ( p [ j ] == '*' && Dfs ( i , j + 1 ));
}
if ( j >= n ) {
return false ;
}
if ( f [ i , j ] != null ) {
return f [ i , j ]. Value ;
}
if ( p [ j ] == '*' ) {
f [ i , j ] = Dfs ( i + 1 , j ) || Dfs ( i + 1 , j + 1 ) || Dfs ( i , j + 1 );
} else {
f [ i , j ] = ( p [ j ] == '?' || s [ i ] == p [ j ]) && Dfs ( i + 1 , j + 1 );
}
return f [ i , j ]. Value ;
}
}
Solution 2: Dynamic Programming
We can convert the memoization search in Solution 1 into dynamic programming.
Define $f[i][j]$ to represent whether the first $i$ characters of string $s$ match the first $j$ characters of string $p$. Initially, $f[0][0] = \textit{true}$, indicating that two empty strings are matching. For $j \in [1, n]$, if $p[j-1] = '*'$, then $f[0][j] = f[0][j-1]$.
Next, we consider the case of $i \in [1, m]$ and $j \in [1, n]$:
If $p[j-1] = '*'$, then $f[i][j] = f[i-1][j] \lor f[i][j-1] \lor f[i-1][j-1]$.
Otherwise, $f[i][j] = (p[j-1] = '?' \lor s[i-1] = p[j-1]) \land f[i-1][j-1]$.
The final answer is $f[m][n]$.
The time complexity is $O(m \times n)$, and the space complexity is $O(m \times n)$. Where $m$ and $n$ are the lengths of the strings $s$ and $p$, respectively.
Python3 Java C++ Go TypeScript PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 class Solution :
def isMatch ( self , s : str , p : str ) -> bool :
m , n = len ( s ), len ( p )
f = [[ False ] * ( n + 1 ) for _ in range ( m + 1 )]
f [ 0 ][ 0 ] = True
for j in range ( 1 , n + 1 ):
if p [ j - 1 ] == "*" :
f [ 0 ][ j ] = f [ 0 ][ j - 1 ]
for i in range ( 1 , m + 1 ):
for j in range ( 1 , n + 1 ):
if p [ j - 1 ] == "*" :
f [ i ][ j ] = f [ i - 1 ][ j ] or f [ i ][ j - 1 ] or f [ i - 1 ][ j - 1 ]
else :
f [ i ][ j ] = f [ i - 1 ][ j - 1 ] and (
p [ j - 1 ] == "?" or s [ i - 1 ] == p [ j - 1 ]
)
return f [ m ][ n ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 class Solution {
public boolean isMatch ( String s , String p ) {
int m = s . length (), n = p . length ();
boolean [][] f = new boolean [ m + 1 ][ n + 1 ] ;
f [ 0 ][ 0 ] = true ;
for ( int j = 1 ; j <= n ; ++ j ) {
if ( p . charAt ( j - 1 ) == '*' ) {
f [ 0 ][ j ] = f [ 0 ][ j - 1 ] ;
}
}
for ( int i = 1 ; i <= m ; ++ i ) {
for ( int j = 1 ; j <= n ; ++ j ) {
if ( p . charAt ( j - 1 ) == '*' ) {
f [ i ][ j ] = f [ i - 1 ][ j ] || f [ i ][ j - 1 ] || f [ i - 1 ][ j - 1 ] ;
} else {
f [ i ][ j ] = f [ i - 1 ][ j - 1 ]
&& ( p . charAt ( j - 1 ) == '?' || s . charAt ( i - 1 ) == p . charAt ( j - 1 ));
}
}
}
return f [ m ][ n ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 class Solution {
public :
bool isMatch ( string s , string p ) {
int m = s . length (), n = p . length ();
bool f [ m + 1 ][ n + 1 ];
memset ( f , false , sizeof ( f ));
f [ 0 ][ 0 ] = true ;
for ( int j = 1 ; j <= n ; ++ j ) {
if ( p [ j - 1 ] == '*' ) {
f [ 0 ][ j ] = f [ 0 ][ j - 1 ];
}
}
for ( int i = 1 ; i <= m ; ++ i ) {
for ( int j = 1 ; j <= n ; ++ j ) {
if ( p [ j - 1 ] == '*' ) {
f [ i ][ j ] = f [ i - 1 ][ j ] || f [ i ][ j - 1 ] || f [ i - 1 ][ j - 1 ];
} else {
f [ i ][ j ] = f [ i - 1 ][ j - 1 ] && ( p [ j - 1 ] == '?' || s [ i - 1 ] == p [ j - 1 ]);
}
}
}
return f [ m ][ n ];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 func isMatch ( s string , p string ) bool {
m , n := len ( s ), len ( p )
f := make ([][] bool , m + 1 )
for i := range f {
f [ i ] = make ([] bool , n + 1 )
}
f [ 0 ][ 0 ] = true
for j := 1 ; j <= n ; j ++ {
if p [ j - 1 ] == '*' {
f [ 0 ][ j ] = f [ 0 ][ j - 1 ]
}
}
for i := 1 ; i <= m ; i ++ {
for j := 1 ; j <= n ; j ++ {
if p [ j - 1 ] == '*' {
f [ i ][ j ] = f [ i - 1 ][ j ] || f [ i ][ j - 1 ] || f [ i - 1 ][ j - 1 ]
} else {
f [ i ][ j ] = f [ i - 1 ][ j - 1 ] && ( p [ j - 1 ] == '?' || s [ i - 1 ] == p [ j - 1 ])
}
}
}
return f [ m ][ n ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 function isMatch ( s : string , p : string ) : boolean {
const m : number = s . length ;
const n : number = p . length ;
const f : boolean [][] = Array . from ({ length : m + 1 }, () =>
Array . from ({ length : n + 1 }, () => false ),
);
f [ 0 ][ 0 ] = true ;
for ( let j = 1 ; j <= n ; ++ j ) {
if ( p . charAt ( j - 1 ) === '*' ) {
f [ 0 ][ j ] = f [ 0 ][ j - 1 ];
}
}
for ( let i = 1 ; i <= m ; ++ i ) {
for ( let j = 1 ; j <= n ; ++ j ) {
if ( p [ j - 1 ] === '*' ) {
f [ i ][ j ] = f [ i - 1 ][ j ] || f [ i ][ j - 1 ] || f [ i - 1 ][ j - 1 ];
} else {
f [ i ][ j ] = f [ i - 1 ][ j - 1 ] && ( p [ j - 1 ] === '?' || s [ i - 1 ] === p [ j - 1 ]);
}
}
}
return f [ m ][ n ];
}
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 class Solution {
/**
* @param string $s
* @param string $p
* @return boolean
*/
function isMatch($s, $p) {
$lengthS = strlen($s);
$lengthP = strlen($p);
$dp = [];
for ($i = 0; $i <= $lengthS; $i++) {
$dp[$i] = array_fill(0, $lengthP + 1, false);
}
$dp[0][0] = true;
for ($i = 1; $i <= $lengthP; $i++) {
if ($p[$i - 1] == '*') {
$dp[0][$i] = $dp[0][$i - 1];
}
}
for ($i = 1; $i <= $lengthS; $i++) {
for ($j = 1; $j <= $lengthP; $j++) {
if ($p[$j - 1] == '?' || $s[$i - 1] == $p[$j - 1]) {
$dp[$i][$j] = $dp[$i - 1][$j - 1];
} elseif ($p[$j - 1] == '*') {
$dp[$i][$j] = $dp[$i][$j - 1] || $dp[$i - 1][$j];
}
}
}
return $dp[$lengthS][$lengthP];
}
}
GitHub