#Problem

#⭐️⭐️⭐️⭐️⭐️

Regular Expression

Follow up: How about includes:

  1. ‘+’, one or more preceding character.
  2. ‘?’, one or none preceding character.

#Solution

Dynamic Programming

dp[i][j] 表示s中前i个字符串和p中前j个字符串是否匹配.

1
2
3
4
5
6
7
8
9
10
11
12
13
if (p[j - 1] == '*') {
dp[i][j] |= dp[i][j - 1]; // exactly one preceding character.
dp[i][j] |= dp[i][j - 2]; // no preceding character.
dp[i][j] |= dp[i - 1][j] && s[i - 1] == p[j - 2]; // multiple preceding character.
} else if (p[j - 1] == '?') {
dp[i][j] |= dp[i][j - 1]; // exactly one preceding character.
dp[i][j] |= dp[i][j - 2]; // no preceding character.
} else if (p[j - 1] == '+') {
dp[i][j] |= dp[i][j - 1]; // exactly one preceding character.
dp[i][j] |= dp[i - 1][j] && s[i - 1] == p[j - 2]; // multiple
} else {
dp[i][j] = dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
}

#Code

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 {
public boolean isMatch(String s, String p) {
if (s.isEmpty() && p.isEmpty()) return true;
if (p.isEmpty()) return false;
int m = s.length();
int n = p.length();
final char[] charS = s.toCharArray();
final char[] charP = p.toCharArray();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int j = 2; j <= n; j++) {
dp[0][j] = dp[0][j - 2] && charP[j - 1] == '*';
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (charP[j - 1] == '.') {
dp[i][j] = dp[i - 1][j - 1];
} else if (charP[j - 1] == '*') {
dp[i][j] = dp[i][j - 1];
dp[i][j] |= dp[i][j - 2];
dp[i][j] |= dp[i - 1][j] && (charS[i - 1] == charP[j - 2] || charP[j - 2] == '.');
} else {
dp[i][j] = dp[i - 1][j - 1] && charS[i - 1] == charP[j - 1];
}
}
}
return dp[m][n];
}
}

Comments