LeetCode 10. Regular Expression Matching

regular-expression-matching.java

/**
 * https://leetcode.com/problems/regular-expression-matching/
 *
 * exponential runtime, O(1) space
 *
 * for isMatch(s, p) where both s and p are not empty
 * 1. if p1 is "*"
 *    a) if s0 equals p0, recursively call isMatch(s.substring(1), p) and isMatch(s, p.substring(2))
 *    b) otherwise, recursively call isMatch(s, p.substring(2))
 * 2. if p1 is not "*"
 *    a) if s0 equals p0, recursively call isMatch(s.substring(1), p.substring(1))
 *    b) otherwise, no match
 */

public class Solution {
    public boolean isMatch(String s, String p) {
        if (s.length() == 0) {
            return checkEmpty(p);
        }
        // now s is not empty
        if (p.length() == 0) {
            return false;
        }
        // now both s and p are not empty
        char s0 = s.charAt(0);
        char p0 = p.charAt(0);
        char p1 = p.length() > 1 ? p.charAt(1) : '0';
        if (p1 == '*') {
            if (compare(s0, p0)) {
                // 1. skip "s0"
                // 2. skip "p0p1"
                // it's possible to use DP to reduce runtime
                return isMatch(s.substring(1), p) || isMatch(s, p.substring(2)); // note that it is isMatch(s, p.substring(2))
                                                                                 // instead of isMatch(s.substring(1), p.substring(2))
                                                                                 // consider s is "a" and p is "a*a"
            } else { // skip "p0p1"
                return isMatch(s, p.substring(2));
            }
        } else {
            if (compare(s0, p0)) { // skip "s0" and "p0"
                return isMatch(s.substring(1), p.substring(1));
            } else {
                return false;
            }
        }
    }
    
    private boolean compare(char s0, char p0) {
        return p0 == '.' || s0 == p0;
    }
    
    // verify that p could be empty
    private boolean checkEmpty(String p) {
        if (p.length() % 2 != 0) { // at least 1 character can't be skipped
            return false;
        }
        for (int i = 1; i < p.length(); i += 2) {
            if (p.charAt(i) != '*') {
                return false;
            }
        }
        return true;
    }
}