# Question

Formatted question description: https://leetcode.ca/all/10.html

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

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

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

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 preceding 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 (.)".


Constraints:

• 1 <= s.length <= 20
• 1 <= p.length <= 20
• s contains only lowercase English letters.
• p contains only lowercase English letters, '.', and '*'.
• It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

# Algorithm

The general idea is as follows:

• If p is empty, if s is also empty, return true, otherwise return false.

• If the length of p is 1, if the length of s is also 1, and the same or p is ‘.’, it returns true, otherwise it returns false.

• If the second character of p is not *, if s is empty at this time, false is returned, otherwise it is judged whether the first character matches, and the recursive function matching is called from the respective second character.

• If the second character of p is *, perform the following loop. The condition is that if s is not empty and the first character matches (including p[0] as a dot), call the recursive function to match s and remove the first two characters of p (The reason for this is to assume that the role of the asterisk at this time is to make the preceding character appear 0 times to verify whether it matches), if the match returns true, otherwise the first letter of s is removed (because the first letter is matched at this time, we can remove the s Because of the asterisk, p can have any initials, so there is no need to remove them), and continue the loop.

• Return the result of calling the recursive function to match s and remove the first two characters of p (the reason for this is to deal with the content that the asterisk cannot match, such as s="ab", p="a*b", and directly enter the while loop Later, we find that “ab” and “b” do not match, so s becomes “

# Code

• /*
* 1. two cases, "*" is 0 or non-0:
* 		1.1: cccbbbaaa matching c*b*a*
* 		1.2: bbbaaa matching c*b*a*
*
*/

public class Regular_Expression_Matching {

public static void main(String[] args) {
Regular_Expression_Matching out = new Regular_Expression_Matching();
Solution s = out.new Solution();

System.out.println(s.isMatch("aa", "a*"));

System.out.println(s.isMatch("aaa", "ab*a")); // false. same as: "aa","b*a"

System.out.println(s.isMatch("cccbbbaaa", "c*b*a*"));
System.out.println(s.isMatch("bbbaaa", "c*b*a*"));

Solution s2 = out.new Solution();
System.out.println(s2.isMatch("aaa", "ab*a")); // false. same as: "aa","b*a"

}

public class Solution_iteration {
public boolean isMatch(String s, String p) {

int i = 0, j = 0, iStar = -1, jStar = -1, m = s.length(), n = p.length();

while (i < m) {
if (j < n && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')) {
++i;
++j;
} else if (j < n && p.charAt(j) == '*') {
iStar = i;
jStar = j++;
} else if (iStar >= 0) {
i = ++iStar;
j = jStar + 1;
} else {
return false;
}
}

while (j < n && p.charAt(j) == '*') {
++j;
}

return j == n;
}
}

public class Solution {
public boolean isMatch(String s, String p) {
if(s == null || p == null) {
return false;
}

if(p.length() == 0) {
return s.length() == 0;
}

if(p.length() == 1) {
// @note: if(p.charAt(0) == "*"), not possible, since * must be following a char, cannot match "aaaaa" with "*", but with "a*"
return (s.length() == 1) && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.' || p.charAt(0) == '*');
}

// now p.length is at least 2
if(p.charAt(1) != '*') { // @note: char is single quote... if(p.charAt(1) != "*") {
if(s.length() == 0) {
return false;
} else {
return (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.') && isMatch(s.substring(1), p.substring(1));
}
}

// now 2nd char of p is "*"
// case 1.1: cccbbbaaa matching c*b*a*
int i = 0;
// @note: 1. missed p.charAt(0) == '.'
// @note: 2. order of conditions, first check if i is out of boundary, then check the rest
// while(s.charAt(i) == p.charAt(0) && i < s.length()) {
// while((s.charAt(i) == p.charAt(0) || p.charAt(0) == '.') && i < s.length()) {
while(i < s.length() && (s.charAt(i) == p.charAt(0) || p.charAt(0) == '.')) { // "aa","b*a"
// one match is enough
if(isMatch(s.substring(i + 1), p.substring(2))) {
return true;
}

i++;
}

// case 1.2: bbbaaa matching c*b*a*
return isMatch(s, p.substring(2));
}
}
}

############

class Solution {
public boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
boolean[][] f = new boolean[m + 1][n + 1];
f[0][0] = true;
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p.charAt(j - 1) == '*') {
f[i][j] = f[i][j - 2];
if (i > 0 && (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1))) {
f[i][j] |= f[i - 1][j];
}
} else if (i > 0
&& (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1))) {
f[i][j] = f[i - 1][j - 1];
}
}
}
return f[m][n];
}
}

• // OJ: https://leetcode.com/problems/regular-expression-matching/
// Time: O(MN)
// Space: O(M)
class Solution {
private:
inline bool matchChar(string &s, int i, string &p, int j) {
return p[j] == '.' ? i < s.size() : s[i] == p[j];
}
bool isMatch(string s, int i, string p, int j) {
if (j == p.size()) return i == s.size();
if (j + 1 < p.size() && p[j + 1] == '*') {
bool ans = false;
while (!(ans = isMatch(s, i, p, j + 2))
&& matchChar(s, i, p, j)) ++i;
return ans;
} else {
return matchChar(s, i, p, j) && isMatch(s, i + 1, p, j + 1);
}
}
public:
bool isMatch(string s, string p) {
return isMatch(s, 0, p, 0);
}
};

• class Solution:
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s), len(p)
f = [[False] * (n + 1) for _ in range(m + 1)]
f[0][0] = True
for i in range(m + 1):
for j in range(1, n + 1):
if p[j - 1] == "*":
f[i][j] = f[i][j - 2]
if i > 0 and (p[j - 2] == "." or s[i - 1] == p[j - 2]):
f[i][j] |= f[i - 1][j]
elif i > 0 and (p[j - 1] == "." or s[i - 1] == p[j - 1]):
f[i][j] = f[i - 1][j - 1]
return f[m][n]

############

class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
dp[0][0] = True
for j in range(1, len(p) + 1):
if p[j - 1] == "*":
dp[0][j] = dp[0][j - 2]

for i in range(1, len(s) + 1):
for j in range(1, len(p) + 1):
if p[j - 1] != "*":
dp[i][j] = dp[i - 1][j - 1] and (s[i - 1] == p[j - 1] or p[j - 1] == ".")
else:
dp[i][j] = dp[i][j - 2] or dp[i - 1][j] and (p[j - 2] == s[i - 1] or p[j - 2] == ".")
return dp[-1][-1]


• func isMatch(s string, p string) bool {
m, n := len(s), len(p)
f := make([][]bool, m+1)
for i := range f {
f[i] = make([]bool, n+1)
}
f[0][0] = true
for i := 0; i <= m; i++ {
for j := 1; j <= n; j++ {
if p[j-1] == '*' {
f[i][j] = f[i][j-2]
if i > 0 && (p[j-2] == '.' || p[j-2] == s[i-1]) {
f[i][j] = f[i][j] || f[i-1][j]
}
} else if i > 0 && (p[j-1] == '.' || p[j-1] == s[i-1]) {
f[i][j] = f[i-1][j-1]
}
}
}
return f[m][n]
}

• /**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function (s, p) {
const m = s.length;
const n = p.length;
const f = Array.from({ length: m + 1 }, () => Array(n + 1).fill(false));
f[0][0] = true;
for (let i = 0; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
if (p[j - 1] === '*') {
f[i][j] = f[i][j - 2];
if (i && (p[j - 2] === '.' || p[j - 2] == s[i - 1])) {
f[i][j] |= f[i - 1][j];
}
} else if (i && (p[j - 1] === '.' || p[j - 1] == s[i - 1])) {
f[i][j] = f[i - 1][j - 1];
}
}
}
return f[m][n];
};


• public class Solution {
public bool IsMatch(string s, string p) {
int m = s.Length, n = p.Length;
bool[,] f = new bool[m + 1, n + 1];
f[0, 0] = true;
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
f[i, j] = f[i, j - 2];
if (i > 0 && (p[j - 2] == '.' || p[j - 2] == s[i - 1])) {
f[i, j] |= f[i - 1, j];
}
} else if (i > 0 && (p[j - 1] == '.' || p[j - 1] == s[i - 1])) {
f[i, j] = f[i - 1, j - 1];
}
}
}
return f[m, n];
}
}