LeetCode: Regular Expression Matching

LeetCode: 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

/**
 * Created by zhouhao on 5/19/2015.
 * <p>
 * Implement regular expression matching with support for '.' and '*'.
 * <pre>
 * '.' Matches any single character.
 * '*' Matches zero or more of the preceding element.
 *
 * The matching should cover the entire input string (not partial).
 *
 * The function prototype should be:
 * bool isMatch(const char *s, const char *p)
 *
 * Some examples:
 * isMatch("aa","a") ��? false
 * isMatch("aa","aa") ��? true
 * isMatch("aaa","aa") ��? false
 * isMatch("aa", "a*") ��? true
 * isMatch("aa", ".*") ��? true
 * isMatch("ab", ".*") ��? true
 * isMatch("aab", "c*a*b") ��? true
 * </pre>
 */
 public class RegularExpressionMatching {
     public boolean isMatch(String s, String p) {
         if (s == null || s.isEmpty()) {
             return emptyable(p);
         }
         if (p == null || p.isEmpty()) {
             return false;
         }
         char cs = s.charAt(0);
         char cp = p.charAt(0);
         char tmp = p.length() > 1 ? p.charAt(1) : '\0';
         if (tmp == '*') {
             if (equalChar(cs, cp)) {
                 return isMatch(s.substring(1), p) || isMatch(s, p.substring(2));
             } else {
                 return isMatch(s, p.substring(2));
             }
         } else {
             return equalChar(cs, cp) && isMatch(s.substring(1), p.substring(1));
         }
     }
     private boolean equalChar(char a, char b) {
         return b == '.' || a == b;
     }
     private boolean emptyable(String s) {
         if (s == null || s.isEmpty()) {
             return true;
         }
         if (s.length() % 2 != 0) {
             return false;
         }
         for (int i = 1; i < s.length(); i = i + 2) {
             if (s.charAt(i) != '*') return false;
         }
         return true;
     }
 }