# 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/