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 (.)".
JAVA
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;
}
}C++
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);
}
};PYTHON
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]JAVASCRIPT
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];
};