/
Regular Expression Matching
66 lines (61 loc) · 2.71 KB
/
Regular Expression Matching
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
public boolean isMatch(String s, String p) {
// make the dp matrix
boolean [][] dp = new boolean[p.length()+1][s.length()+1];
for(int i=0;i<dp.length;i++)
{
for(int j=0;j<dp[0].length;j++)
{
// marking the blank space as true
if(i==0 && j==0)
{
dp[0][0]=true;
}
// first row as false
else if(i==0)
{
dp[0][j] = false;
}
//first column as false but have to check two rows above where there is *
// this is because * can become black by not including anything
else if(j==0)
{
char ch =p.charAt(i-1);
if(ch == '*')
dp[i][j]=dp[i-2][j]; // if star in first column then we can make a blank so we check two rows above
else
dp[i][j]=false;
}
// processing for normal cells in the dp
else
{
// if the character in string and pattern match or pattern charcter is '.' then check diagonally (top-left)
// if true then here it is true too
if(p.charAt(i-1) == s.charAt(j-1) || p.charAt(i-1) == '.' )
{
dp[i][j]=dp[i-1][j-1];
}
// else if a star is found then we check two rows above if true then continue for next iteration, here star
//has been used to make a blank
else if(p.charAt(i-1) == '*' )
{
dp[i][j]=dp[i-2][j];
if(dp[i][j])
{
continue;
}
// if being blank returns false then we check if the previous character to the star matches the string s last character
// this is done to show that the * has two options that either to remain blank and remove itself and its previous
// character from the pattern p or multiply and release another of the p.charAt(i-2) character, we then move left to check
// in the dp table if this is true or not ** (explaine in images)
if( p.charAt(i-2) == s.charAt(j-1) || p.charAt(i-2) == '.')
{
dp[i][j]=dp[i][j-1];
}
}
}
}
}
return dp[p.length()][s.length()];
}
}