Regular Expression Matching Leetcode Solution
Regular Expression Matching Leetcode Problem
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 :
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Regular Expression Matching Leetcode Solution :
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.
Example 1:
Input: s = “aa”, p = “a*”
Output: true
Example 2:
Input: s = “ab”, p = “.*”
Output: true
In the “Two Sum” problem, you are 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.
Example 1 :
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 2 :
Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Approach :
For Solving two sum Leetcode Problem we can use following procedure :
- If the pattern is empty, return True if the text is also empty (base case).
- Check if the first characters of the text and pattern match, considering ‘.’ as a wildcard character.
- If the next character in the pattern is ”, there are two possibilities:
a. Ignore the ” and the preceding character in the pattern and continue matching the text with the shortened pattern.
b. Keep the preceding character in the pattern and match the next character in the text. - If there is no ‘*’ in the pattern, simply match the next characters in the text and pattern.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
C++
Java
Python
C++
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
vector> dp(m + 1, vector(n + 1, false));
dp[0][0] = true;
for (int i = 0; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p[j - 1] == '*') {
dp[i][j] = dp[i][j - 2] || (i && dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
} else {
dp[i][j] = i && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
}
}
}
return dp[m][n];
}
};
Java
class Solution {
public boolean isMatch(String s, String p) {
if (p == null || p.length() == 0) return (s == null || s.length() == 0);
boolean dp[][] = new boolean[s.length()+1][p.length()+1];
dp[0][0] = true;
for (int j=2; j<=p.length(); j++) {
dp[0][j] = p.charAt(j-1) == '*' && dp[0][j-2];
}
for (int j=1; j<=p.length(); j++) {
for (int i=1; i<=s.length(); i++) {
if (p.charAt(j-1) == s.charAt(i-1) || p.charAt(j-1) == '.')
dp[i][j] = dp[i-1][j-1];
else if(p.charAt(j-1) == '*')
dp[i][j] = dp[i][j-2] || ((s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2) == '.') && dp[i-1][j]);
}
}
return dp[s.length()][p.length()];
}
}
Python
def isMatch(s, p):
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] == s[i - 1] or p[j - 1] == '.':
dp[i][j] = dp[i - 1][j - 1]
elif p[j - 1] == '*':
dp[i][j] = dp[i][j - 2] or (dp[i - 1][j] and (s[i - 1] == p[j - 2] or p[j - 2] == '.'))
return dp[len(s)][len(p)]
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment