Regular Expression Matching Problem

Regular Expression Matching 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 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 Problem Solution

Problem Solution In Python

class Solution:
    def isMatch(self, s, p):
        matches = [[False for j in range(len(s) + 1)] for i in range(len(p) + 1)]
        matches[0][0] = True
        for i in range(2, len(p) + 1):
            if p[i - 1] == "*": 
                matches[i][0] = matches[i - 2][0]
        for i in range(1, len(p) + 1):
            for j in range(1, len(s) + 1):
                if p[i -1] == s[j - 1] or p[i - 1] == ".":
                    matches[i][j] = matches[i - 1][j - 1]
                elif p[i - 1] == "*": 
                    if p[i - 2] != s[j - 1] and p[i - 2] != ".":
                        matches[i][j] = matches[i - 2][j]
                    else:
                        matches[i][j] = matches[i - 2][j] or matches[i -1][j] or matches[i][j - 1] 
        return matches[-1][-1]

Problem Solution In Java

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()];
    }

Problem Solution In C++

class Solution {
public:
    bool isMatch(string s, string p) {
        int m=s.length(),n=p.length();
        bool dp[m+1][n+1];
        memset(dp,false,sizeof(dp));dp[0][0]=true;
        for(int i=0;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(p[j-1]!='.' && p[j-1]!='*')
                {
                    if(i>0 && s[i-1]==p[j-1] && dp[i-1][j-1])
                        dp[i][j]=true;
                }
                else if(p[j-1]=='.')
                {
                    if(i>0 && dp[i-1][j-1])
                        dp[i][j]=true;
                }
                else if(j>1)
                {
                    if(dp[i][j-1] || dp[i][j-2])
                        dp[i][j]=true;
                    else if(i>0 && (p[j-2]==s[i-1] || p[j-2]=='.') && dp[i-1][j] )
                        dp[i][j]=true;
                }
            }
        }
        return dp[m][n];
    }
};

Problem Solution In C

bool isMatch(char* s, char* p) {
    for (;*p && *(p + 1) != '*'; ++s, ++p)
        if (!*s || (*p != *s && *p != '.'))
            return false;
        
    if (!*p)
        return *s == 0;
    
    if (*s && (*s == *p || *p == '.'))
        return isMatch(s, p + 2) || isMatch(s + 1, p);
    else
        return isMatch(s, p + 2);
}

If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment