PROBLEM DESCRIPTION
Given an input string s and a pattern p, implement regular expression matching with support for ‘.’ and ‘*’ where:
- ’.’ Matches any single character.
- ‘*’ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
SOLUTION
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
67
68
69
70
71
72
73
class Solution {
public boolean isMatch(String s, String p) {
return matchHelper(s, p, s.length()-1, p.length()-1, new HashMap<String, Boolean>());
}
public boolean matchHelper(String s, String p, int i, int j, Map<String, Boolean> map){
//if all characters in s and p are over, return true
if(i == -1 && j == -1) return true;
//if there are no characters in the pattern, but characters in s are still left
if(j == -1) return false;
//IMPORTANT
//if there are no characters in s but patter is remaining
//Example:
//string s = "a", p="b*c*a*"
if(i == -1){
//loop through remaining characters in the pattern
for(int k=j; k>=0; k--){
//if the character in pattern is *, it should be okay as we can take zero instances of preceding character
//for next iteration, we need to move 2 characters back
if(p.charAt(k) == '*'){
k--; //we need to move 2 characters back. k-- here, and another one will be done by for loop
}else{
//if the next character is not *, return false as there is nothing in the string s which can match it
return false;
}
}
return true;
}
if(!map.containsKey(i+":"+j)){
boolean match = false;
//if characters in the string and pattern match OR pattern has "." which can match with a single character
if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.'){
//check the remaining characters in string and pattern
//so we reduce both i and j by 1
match = matchHelper(s, p, i-1, j-1, map);
//otherwise, check if pattern has a *
}else if(p.charAt(j) == '*'){
//we can match the * with empty character
//so, i will remain at the same position
//but, j will move by 2 steps (as we need to skip the preceding element too - like [a*])
match = matchHelper(s, p, i, j-2, map);
//if the preciding element patches the mattern of if it's a "." which would match with any characters
if(s.charAt(i) == p.charAt(j-1) || p.charAt(j-1) == '.'){
//move index i by 1 as we can match 1 character
//IMPORTANT: we will keep the j at the same position so that it can continue to match further if there are more instances of the same char
match = match || matchHelper(s, p, i-1, j, map);
}
}//else match is not found
map.put(i+":"+j, match);
}
return map.get(i+":"+j);
}
}