Regular Expression Matching LeetCode Solution

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

Regular Expression Matching LeetCode Solution

Problem Statement ->

Given an input string 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)