[Link] https://leetcode.com/problems/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
class Solution {
public boolean isMatch(String s, String p) {
return test(s, p, 0, 0);
}
public boolean test(String s, String p, int sIdx, int pIdx) {
if(pIdx >= p.length()) return sIdx == s.length() ? true : false;
if(sIdx == s.length()) {
if(pIdx + 1 < p.length()) return p.charAt(pIdx + 1) == '*' ? test(s, p, sIdx, pIdx + 2) : false;
else return false;
} else {
if(p.charAt(pIdx) == '.') {
if(pIdx + 1 < p.length() && p.charAt(pIdx + 1) == '*') { //. *
for(int i = sIdx; i <= s.length(); i++) if(test(s, p, i, pIdx + 2)) return true;
return false;
} else return test(s,p, sIdx + 1, pIdx + 1); //only .
} else { //alphabet
if(pIdx + 1 < p.length() && p.charAt(pIdx + 1) == '*') { //alphabet *
for(int i = sIdx; i <= s.length(); i++) {
if(test(s, p, i, pIdx + 2)) return true;
if(i!= s.length() && s.charAt(i) != p.charAt(pIdx)) break;
}
return false;
} else return s.charAt(sIdx) == p.charAt(pIdx) ? test(s,p, sIdx + 1, pIdx + 1) : false;
}
}
}
}