ProjectAlgorithms/codes/java/RegularExpressionMatching.java at main · Sayakb03/ProjectAlgorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
classSolution {
publicbooleanisMatch(Stringtext, Stringpattern) {
boolean[][] dp = newboolean[text.length() + 1][pattern.length() + 1];
dp[text.length()][pattern.length()] = true;

for (inti = text.length(); i >= 0; i--){
for (intj = pattern.length() - 1; j >= 0; j--){
booleanfirst_match = (i < text.length() &&
 (pattern.charAt(j) == text.charAt(i) ||
pattern.charAt(j) == '.'));
if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
 } else {
dp[i][j] = first_match && dp[i+1][j+1];
 }
 }
 }
returndp[0][0];
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
classSolution {
publicbooleanisMatch(Stringtext, Stringpattern) {
boolean[][] dp = newboolean[text.length() + 1][pattern.length() + 1];
dp[text.length()][pattern.length()] = true;

for (inti = text.length(); i >= 0; i--){
for (intj = pattern.length() - 1; j >= 0; j--){
booleanfirst_match = (i < text.length() &&
 (pattern.charAt(j) == text.charAt(i) ||
pattern.charAt(j) == '.'));
if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
 } else {
dp[i][j] = first_match && dp[i+1][j+1];
 }
 }
 }
returndp[0][0];
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
classSolution {
publicbooleanisMatch(Stringtext, Stringpattern) {
boolean[][] dp = newboolean[text.length() + 1][pattern.length() + 1];
dp[text.length()][pattern.length()] = true;

for (inti = text.length(); i >= 0; i--){
for (intj = pattern.length() - 1; j >= 0; j--){
booleanfirst_match = (i < text.length() &&
 (pattern.charAt(j) == text.charAt(i) ||
pattern.charAt(j) == '.'));
if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
 } else {
dp[i][j] = first_match && dp[i+1][j+1];
 }
 }
 }
returndp[0][0];
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
classSolution {
publicbooleanisMatch(Stringtext, Stringpattern) {
boolean[][] dp = newboolean[text.length() + 1][pattern.length() + 1];
dp[text.length()][pattern.length()] = true;

for (inti = text.length(); i >= 0; i--){
for (intj = pattern.length() - 1; j >= 0; j--){
booleanfirst_match = (i < text.length() &&
 (pattern.charAt(j) == text.charAt(i) ||
pattern.charAt(j) == '.'));
if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
 } else {
dp[i][j] = first_match && dp[i+1][j+1];
 }
 }
 }
returndp[0][0];
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
classSolution {
publicbooleanisMatch(Stringtext, Stringpattern) {
boolean[][] dp = newboolean[text.length() + 1][pattern.length() + 1];
dp[text.length()][pattern.length()] = true;

for (inti = text.length(); i >= 0; i--){
for (intj = pattern.length() - 1; j >= 0; j--){
booleanfirst_match = (i < text.length() &&
 (pattern.charAt(j) == text.charAt(i) ||
pattern.charAt(j) == '.'));
if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
 } else {
dp[i][j] = first_match && dp[i+1][j+1];
 }
 }
 }
returndp[0][0];
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
classSolution {
publicbooleanisMatch(Stringtext, Stringpattern) {
boolean[][] dp = newboolean[text.length() + 1][pattern.length() + 1];
dp[text.length()][pattern.length()] = true;

for (inti = text.length(); i >= 0; i--){
for (intj = pattern.length() - 1; j >= 0; j--){
booleanfirst_match = (i < text.length() &&
 (pattern.charAt(j) == text.charAt(i) ||
pattern.charAt(j) == '.'));
if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
 } else {
dp[i][j] = first_match && dp[i+1][j+1];
 }
 }
 }
returndp[0][0];
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
classSolution {
publicbooleanisMatch(Stringtext, Stringpattern) {
boolean[][] dp = newboolean[text.length() + 1][pattern.length() + 1];
dp[text.length()][pattern.length()] = true;

for (inti = text.length(); i >= 0; i--){
for (intj = pattern.length() - 1; j >= 0; j--){
booleanfirst_match = (i < text.length() &&
 (pattern.charAt(j) == text.charAt(i) ||
pattern.charAt(j) == '.'));
if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
 } else {
dp[i][j] = first_match && dp[i+1][j+1];
 }
 }
 }
returndp[0][0];
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
classSolution {
publicbooleanisMatch(Stringtext, Stringpattern) {
boolean[][] dp = newboolean[text.length() + 1][pattern.length() + 1];
dp[text.length()][pattern.length()] = true;

for (inti = text.length(); i >= 0; i--){
for (intj = pattern.length() - 1; j >= 0; j--){
booleanfirst_match = (i < text.length() &&
 (pattern.charAt(j) == text.charAt(i) ||
pattern.charAt(j) == '.'));
if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
 } else {
dp[i][j] = first_match && dp[i+1][j+1];
 }
 }
 }
returndp[0][0];
 }
}