10. Regular Expression Matching (Hard)

https://leetcode.com/problems/regular-expression-matching/

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".

Example 5:

Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

Solutions

class Solution {

    // This problem is a little bit complicated, do not waste too much time and effort.

    // The problem requires to match up the entire target string, rather than the partial match.
    // The key point of resolve this problem is to handle every * respectively.

    // When dealing with *, be careful that it must be used with preceding element,
    // which means a single * without prefix is a wrong case.

    // And be careful that * could mean 0 or >=1 preceding elements, both cases need to be
    // treated differently,

    public boolean isMatch(String s, String p) {
        if (p.length() == 0) {
            return s.length() == 0;
        }

        // when p.length == 1, consists of 3 situations
        // from the perspective of recursion, this condition should be the exit of searching.
        if (p.length() == 1) {
            // Notice that p cannot be * since it needs prefix elements and the situation
            // becomes simplified.

            // s.length() must be 1, p could be . or other char.
            // to match s, p's length must be 1, otherwise s cannot be covered by p
            if (s.length() != 1) {
                return false;
            }

            //if the first does not match, return false
            if (p.charAt(0) != s.charAt(0) && p.charAt(0) != '.') {
                return false;
            }

            // otherwise, compare the rest of the string of s and p.

            return isMatch(s.substring(1), p.substring(1));
        }

        // when the second char of p is not '*'
        if (p.charAt(1) != '*') {
            if (s.length() < 1) {
                return false;
            }

            // what if s="ss", p="*s" ? Strictly speaking, * is used to match preceding element,
            // can not be situated at the head of string.

            // And . can be used at the leftmost position since it matches any single character
            if (p.charAt(0) != s.charAt(0) && p.charAt(0) != '.') {
                return false;
            } else {
                // p.charAt(0) == s.charAt(0) || p.charAt(0) == '.'

                return isMatch(s.substring(1), p.substring(1));
            }
        }

        // when the second char of p is '*'

        // both the following two cases must be checked simultaneous and equally.

        // check case 1 that * means 0 preceding element
        if (isMatch(s, p.substring(2))) {
            return true;
        }

        // check case 2 that * stands for 1 or more preceding element,
        // so try all the possible substrings
        int i = 0;
        while (i < s.length() && (s.charAt(i) == p.charAt(0) || p.charAt(0) == '.')) {
            if (isMatch(s.substring(i + 1), p.substring(2))) {
                return true;
            }

            i++;
        }

        return false;
    }
}

Reference

https://www.programcreek.com/2012/12/leetcode-regular-expression-matching-in-java/

Incorrect Solutions

References