递归
字符串
动态规划
题目描述
给你一个字符串 s
和一个字符规律 p
,请你来实现一个支持 '.'
和 '*'
的正则表达式匹配。
'.'
匹配任意单个字符
'*'
匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s
的,而不是部分字符串。
示例 1:
输入: s = "aa", p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入: s = "aa", p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:
输入: s = "ab", p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。
提示:
1 <= s.length <= 20
1 <= p.length <= 20
s
只包含从 a-z
的小写字母。
p
只包含从 a-z
的小写字母,以及字符 .
和 *
。
保证每次出现字符 *
时,前面都匹配到有效的字符
解法
方法一:记忆化搜索
我们设计一个函数 $dfs(i, j)$,表示从 $s$ 的第 $i$ 个字符开始,和 $p$ 的第 $j$ 个字符开始是否匹配。那么答案就是 $dfs(0, 0)$。
函数 $dfs(i, j)$ 的计算过程如下:
如果 $j$ 已经到达 $p$ 的末尾,那么如果 $i$ 也到达了 $s$ 的末尾,那么匹配成功,否则匹配失败。
如果 $j$ 的下一个字符是 '*'
,我们可以选择匹配 $0$ 个 $s[i]$ 字符,那么就是 $dfs(i, j + 2)$。如果此时 $i \lt m$ 并且 $s[i]$ 和 $p[j]$ 匹配,那么我们可以选择匹配 $1$ 个 $s[i]$ 字符,那么就是 $dfs(i + 1, j)$。
如果 $j$ 的下一个字符不是 '*'
,那么如果 $i \lt m$ 并且 $s[i]$ 和 $p[j]$ 匹配,那么就是 $dfs(i + 1, j + 1)$。否则匹配失败。
过程中,我们可以使用记忆化搜索,避免重复计算。
时间复杂度 $O(m \times n)$,空间复杂度 $O(m \times n)$。其中 $m$ 和 $n$ 分别是 $s$ 和 $p$ 的长度。
Python3 Java C++ Go Rust JavaScript C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14 class Solution :
def isMatch ( self , s : str , p : str ) -> bool :
@cache
def dfs ( i , j ):
if j >= n :
return i == m
if j + 1 < n and p [ j + 1 ] == '*' :
return dfs ( i , j + 2 ) or (
i < m and ( s [ i ] == p [ j ] or p [ j ] == '.' ) and dfs ( i + 1 , j )
)
return i < m and ( s [ i ] == p [ j ] or p [ j ] == '.' ) and dfs ( i + 1 , j + 1 )
m , n = len ( s ), len ( p )
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 class Solution {
private Boolean [][] f ;
private String s ;
private String p ;
private int m ;
private int n ;
public boolean isMatch ( String s , String p ) {
m = s . length ();
n = p . length ();
f = new Boolean [ m + 1 ][ n + 1 ] ;
this . s = s ;
this . p = p ;
return dfs ( 0 , 0 );
}
private boolean dfs ( int i , int j ) {
if ( j >= n ) {
return i == m ;
}
if ( f [ i ][ j ] != null ) {
return f [ i ][ j ] ;
}
boolean res = false ;
if ( j + 1 < n && p . charAt ( j + 1 ) == '*' ) {
res = dfs ( i , j + 2 )
|| ( i < m && ( s . charAt ( i ) == p . charAt ( j ) || p . charAt ( j ) == '.' ) && dfs ( i + 1 , j ));
} else {
res = i < m && ( s . charAt ( i ) == p . charAt ( j ) || p . charAt ( j ) == '.' ) && dfs ( i + 1 , j + 1 );
}
return f [ i ][ j ] = res ;
}
}
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 class Solution {
public :
bool isMatch ( string s , string p ) {
int m = s . size (), n = p . size ();
int f [ m + 1 ][ n + 1 ];
memset ( f , 0 , sizeof f );
function < bool ( int , int ) > dfs = [ & ]( int i , int j ) -> bool {
if ( j >= n ) {
return i == m ;
}
if ( f [ i ][ j ]) {
return f [ i ][ j ] == 1 ;
}
int res = -1 ;
if ( j + 1 < n && p [ j + 1 ] == '*' ) {
if ( dfs ( i , j + 2 ) or ( i < m and ( s [ i ] == p [ j ] or p [ j ] == '.' ) and dfs ( i + 1 , j ))) {
res = 1 ;
}
} else if ( i < m and ( s [ i ] == p [ j ] or p [ j ] == '.' ) and dfs ( i + 1 , j + 1 )) {
res = 1 ;
}
f [ i ][ j ] = res ;
return res == 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 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 j >= n {
return i == m
}
if f [ i ][ j ] != 0 {
return f [ i ][ j ] == 1
}
res := - 1
if j + 1 < n && p [ j + 1 ] == '*' {
if dfs ( i , j + 2 ) || ( i < m && ( s [ i ] == p [ j ] || p [ j ] == '.' ) && dfs ( i + 1 , j )) {
res = 1
}
} else if i < m && ( s [ i ] == p [ j ] || p [ j ] == '.' ) && dfs ( i + 1 , j + 1 ) {
res = 1
}
f [ i ][ j ] = res
return res == 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
35
36
37
38 impl Solution {
#[allow(dead_code)]
pub fn is_match ( s : String , p : String ) -> bool {
let n = s . len ();
let m = p . len ();
let s = s . chars (). collect :: < Vec < char >> ();
let p = p . chars (). collect :: < Vec < char >> ();
let mut dp = vec! [ vec! [ false ; m + 1 ]; n + 1 ];
// Initialize the dp vector
dp [ 0 ][ 0 ] = true ;
for i in 1 ..= m {
if p [ i - 1 ] == '*' {
dp [ 0 ][ i ] = dp [ 0 ][ i - 2 ];
}
}
// Begin the actual dp process
for i in 1 ..= n {
for j in 1 ..= m {
if s [ i - 1 ] == p [ j - 1 ] || p [ j - 1 ] == '.' {
dp [ i ][ j ] = dp [ i - 1 ][ j - 1 ];
}
if p [ j - 1 ] == '*' {
if j >= 2 && ( s [ i - 1 ] == p [ j - 2 ] || p [ j - 2 ] == '.' ) {
dp [ i ][ j ] = dp [ i - 1 ][ j ] || dp [ i ][ j - 2 ];
} else if j >= 2 && s [ i - 1 ] != p [ j - 2 ] {
dp [ i ][ j ] = dp [ i ][ j - 2 ];
}
}
}
}
dp [ n ][ m ]
}
}
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 /**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function ( s , p ) {
const m = s . length ;
const n = p . length ;
const f = Array . from ({ length : m + 1 }, () => Array ( n + 1 ). fill ( 0 ));
const dfs = ( i , j ) => {
if ( j >= n ) {
return i === m ;
}
if ( f [ i ][ j ]) {
return f [ i ][ j ] === 1 ;
}
let res = - 1 ;
if ( j + 1 < n && p [ j + 1 ] === '*' ) {
if ( dfs ( i , j + 2 ) || ( i < m && ( s [ i ] === p [ j ] || p [ j ] === '.' ) && dfs ( i + 1 , j ))) {
res = 1 ;
}
} else if ( i < m && ( s [ i ] === p [ j ] || p [ j ] === '.' ) && dfs ( i + 1 , j + 1 )) {
res = 1 ;
}
f [ i ][ j ] = res ;
return res === 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
35 public class Solution {
private string s ;
private string p ;
private int m ;
private int n ;
private int [,] f ;
public bool IsMatch ( string s , string p ) {
m = s . Length ;
n = p . Length ;
f = new int [ m + 1 , n + 1 ];
this . s = s ;
this . p = p ;
return dfs ( 0 , 0 );
}
private bool dfs ( int i , int j ) {
if ( j >= n ) {
return i == m ;
}
if ( f [ i , j ] != 0 ) {
return f [ i , j ] == 1 ;
}
int res = - 1 ;
if ( j + 1 < n && p [ j + 1 ] == '*' ) {
if ( dfs ( i , j + 2 ) || ( i < m && ( s [ i ] == p [ j ] || p [ j ] == '.' ) && dfs ( i + 1 , j ))) {
res = 1 ;
}
} else if ( i < m && ( s [ i ] == p [ j ] || p [ j ] == '.' ) && dfs ( i + 1 , j + 1 )) {
res = 1 ;
}
f [ i , j ] = res ;
return res == 1 ;
}
}
方法二:动态规划
我们可以将方法一中的记忆化搜索转换为动态规划。
定义 $f[i][j]$ 表示字符串 $s$ 的前 $i$ 个字符和字符串 $p$ 的前 $j$ 个字符是否匹配。那么答案就是 $f[m][n]$。初始化 $f[0][0] = true$,表示空字符串和空正则表达式是匹配的。
与方法一类似,我们可以分情况来讨论。
如果 $p[j - 1]$ 是 '*'
,那么我们可以选择匹配 $0$ 个 $s[i - 1]$ 字符,那么就是 $f[i][j] = f[i][j - 2]$。如果此时 $s[i - 1]$ 和 $p[j - 2]$ 匹配,那么我们可以选择匹配 $1$ 个 $s[i - 1]$ 字符,那么就是 $f[i][j] = f[i][j] \lor f[i - 1][j]$。
如果 $p[j - 1]$ 不是 '*'
,那么如果 $s[i - 1]$ 和 $p[j - 1]$ 匹配,那么就是 $f[i][j] = f[i - 1][j - 1]$。否则匹配失败。
时间复杂度 $O(m \times n)$,空间复杂度 $O(m \times n)$。其中 $m$ 和 $n$ 分别是 $s$ 和 $p$ 的长度。
Python3 Java C++ Go JavaScript C# PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14 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 i in range ( m + 1 ):
for j in range ( 1 , n + 1 ):
if p [ j - 1 ] == "*" :
f [ i ][ j ] = f [ i ][ j - 2 ]
if i > 0 and ( p [ j - 2 ] == "." or s [ i - 1 ] == p [ j - 2 ]):
f [ i ][ j ] |= f [ i - 1 ][ j ]
elif i > 0 and ( p [ j - 1 ] == "." or s [ i - 1 ] == p [ j - 1 ]):
f [ i ][ j ] = f [ i - 1 ][ 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 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 i = 0 ; i <= m ; ++ i ) {
for ( int j = 1 ; j <= n ; ++ j ) {
if ( p . charAt ( j - 1 ) == '*' ) {
f [ i ][ j ] = f [ i ][ j - 2 ] ;
if ( i > 0 && ( p . charAt ( j - 2 ) == '.' || p . charAt ( j - 2 ) == s . charAt ( i - 1 ))) {
f [ i ][ j ] |= f [ i - 1 ][ j ] ;
}
} else if ( i > 0
&& ( p . charAt ( j - 1 ) == '.' || p . charAt ( j - 1 ) == s . charAt ( i - 1 ))) {
f [ i ][ j ] = f [ i - 1 ][ 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 class Solution {
public :
bool isMatch ( string s , string p ) {
int m = s . size (), n = p . size ();
bool f [ m + 1 ][ n + 1 ];
memset ( f , false , sizeof f );
f [ 0 ][ 0 ] = true ;
for ( int i = 0 ; i <= m ; ++ i ) {
for ( int j = 1 ; j <= n ; ++ j ) {
if ( p [ j - 1 ] == '*' ) {
f [ i ][ j ] = f [ i ][ j - 2 ];
if ( i && ( p [ j - 2 ] == '.' || p [ j - 2 ] == s [ i - 1 ])) {
f [ i ][ j ] |= f [ i - 1 ][ j ];
}
} else if ( i && ( p [ j - 1 ] == '.' || p [ j - 1 ] == s [ i - 1 ])) {
f [ i ][ j ] = f [ i - 1 ][ 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 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 i := 0 ; i <= m ; i ++ {
for j := 1 ; j <= n ; j ++ {
if p [ j - 1 ] == '*' {
f [ i ][ j ] = f [ i ][ j - 2 ]
if i > 0 && ( p [ j - 2 ] == '.' || p [ j - 2 ] == s [ i - 1 ]) {
f [ i ][ j ] = f [ i ][ j ] || f [ i - 1 ][ j ]
}
} else if i > 0 && ( p [ j - 1 ] == '.' || p [ j - 1 ] == s [ i - 1 ]) {
f [ i ][ j ] = f [ i - 1 ][ 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 /**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function ( s , p ) {
const m = s . length ;
const n = p . length ;
const f = Array . from ({ length : m + 1 }, () => Array ( n + 1 ). fill ( false ));
f [ 0 ][ 0 ] = true ;
for ( let i = 0 ; i <= m ; ++ i ) {
for ( let j = 1 ; j <= n ; ++ j ) {
if ( p [ j - 1 ] === '*' ) {
f [ i ][ j ] = f [ i ][ j - 2 ];
if ( i && ( p [ j - 2 ] === '.' || p [ j - 2 ] === s [ i - 1 ])) {
f [ i ][ j ] |= f [ i - 1 ][ j ];
}
} else if ( i && ( p [ j - 1 ] === '.' || p [ j - 1 ] === s [ i - 1 ])) {
f [ i ][ j ] = f [ i - 1 ][ 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 public class Solution {
public bool IsMatch ( string s , string p ) {
int m = s . Length , n = p . Length ;
bool [,] f = new bool [ m + 1 , n + 1 ];
f [ 0 , 0 ] = true ;
for ( int i = 0 ; i <= m ; ++ i ) {
for ( int j = 1 ; j <= n ; ++ j ) {
if ( p [ j - 1 ] == '*' ) {
f [ i , j ] = f [ i , j - 2 ];
if ( i > 0 && ( p [ j - 2 ] == '.' || p [ j - 2 ] == s [ i - 1 ])) {
f [ i , j ] |= f [ i - 1 , j ];
}
} else if ( i > 0 && ( p [ j - 1 ] == '.' || p [ j - 1 ] == s [ i - 1 ])) {
f [ i , j ] = f [ i - 1 , 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
34
35
36
37
38 class Solution {
/**
* @param string $s
* @param string $p
* @return boolean
*/
function isMatch($s, $p) {
$m = strlen($s);
$n = strlen($p);
$dp = array_fill(0, $m + 1, array_fill(0, $n + 1, false));
$dp[0][0] = true;
for ($j = 1; $j <= $n; $j++) {
if ($p[$j - 1] == '*') {
$dp[0][$j] = $dp[0][$j - 2];
}
}
for ($i = 1; $i <= $m; $i++) {
for ($j = 1; $j <= $n; $j++) {
if ($p[$j - 1] == '.' || $p[$j - 1] == $s[$i - 1]) {
$dp[$i][$j] = $dp[$i - 1][$j - 1];
} elseif ($p[$j - 1] == '*') {
$dp[$i][$j] = $dp[$i][$j - 2];
if ($p[$j - 2] == '.' || $p[$j - 2] == $s[$i - 1]) {
$dp[$i][$j] = $dp[$i][$j] || $dp[$i - 1][$j];
}
} else {
$dp[$i][$j] = false;
}
}
}
return $dp[$m][$n];
}
}