Here, We see Regular Expression Matching problem Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

Regular Expression Matching LeetCode Solution
Problem Statement ->
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 (.)".
Regular Expression Matching Leetcode Solution C++ ->
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
vector<bool> pre(n + 1, false), cur(n + 1, false);
cur[0] = true;
for (int i = 0; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p[j - 1] == '*') {
cur[j] = cur[j - 2] || (i && pre[j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
} else {
cur[j] = i && pre[j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
}
}
fill(pre.begin(), pre.end(), false);
swap(pre, cur);
}
return pre[n];
}
};
Code language: C++ (cpp)
Regular Expression Matching Leetcode Solution Java ->
class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
boolean[][] dp = new boolean[s.length()+1][p.length()+1];
dp[0][0] = true;
for (int i = 0; i < p.length(); i++) {
if (p.charAt(i) == '*' && dp[0][i-1]) {
dp[0][i+1] = true;
}
}
for (int i = 0 ; i < s.length(); i++) {
for (int j = 0; j < p.length(); j++) {
if (p.charAt(j) == '.') {
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == s.charAt(i)) {
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == '*') {
if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
dp[i+1][j+1] = dp[i+1][j-1];
} else {
dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
}
}
}
}
return dp[s.length()][p.length()];
}
}
Code language: Java (java)
Regular Expression Matching Leetcode Solution JavaScript ->
var isMatch = function(s, p) {
var lenS = s.length;
var lenP = p.length;
var map = {};
return check(0, 0);
function check(idxS, idxP) {
if (map[idxS + ':' + idxP] !== undefined) return map[idxS + ':' + idxP];
if (idxS > lenS) return false;
if (idxS === lenS && idxP === lenP) return true;
if (p[idxP] === '.' || p[idxP] === s[idxS]) {
map[idxS + ':' + idxP] = p[idxP + 1] === '*' ?
check(idxS + 1, idxP) || check(idxS, idxP + 2) :
check(idxS + 1, idxP + 1);
} else {
map[idxS + ':' + idxP] = p[idxP + 1] === '*' ?
check(idxS, idxP + 2) : false;
}
return map[idxS + ':' + idxP];
}
};
Code language: JavaScript (javascript)
Regular Expression Matching Leetcode Solution Python ->
class Solution(object):
def isMatch(self, s, p):
dp = [[False] * (len(s) + 1) for _ in range(len(p) + 1)]
dp[0][0] = True
for i in range(1, len(p)):
dp[i + 1][0] = dp[i - 1][0] and p[i] == '*'
for i in range(len(p)):
for j in range(len(s)):
if p[i] == '*':
dp[i + 1][j + 1] = dp[i - 1][j + 1] or dp[i][j + 1]
if p[i - 1] == s[j] or p[i - 1] == '.':
dp[i + 1][j + 1] |= dp[i + 1][j]
else:
dp[i + 1][j + 1] = dp[i][j] and (p[i] == s[j] or p[i] == '.')
return dp[-1][-1]
Code language: Python (python)