[BUG] - Invalid Testcase

LeetCode Username

mudit_2904

Problem Number, Title, and Link

Regular Expression Matching https://leetcode.com/problems/regular-expression-matching/

Bug Category

Incorrect test case (Output of test case is incorrect as per the problem statement)

Bug Description

The testcase doesn't return expected output as per question description.

Language Used for Code

C++

Code used for Submit/Run operation

class Solution {
public:
    bool chk(int i, int j, string &s, string &p){
        if(i >= 0 && j < 0)
            return false;
        if(i < 0){
            while(j >= 0){
                if(p[j] != '*')
                    return false;
                j--;
            }
            return true;
        }

        if(s[i] == p[j] || p[j] == '.')
            return chk(i - 1, j - 1, s, p);
        else if(p[j] == '*')
            return chk(i, j - 1, s, p) || chk(i - 1, j, s, p);
        return false;
    }

    bool isMatch(string s, string p) {

        return chk(s.size() - 1, p.size() - 1, s, p);
    }
};

Expected behavior

s="a" p="c*a" The expected output should be "false", but it says "true", which is invalid because string "s" won't completely match with string "p" because the first character of string "p" is 'c' which is not the first character of string "s"

Furthermore, let's look at second test case: s="mississippi" p="misisp." The expected output should be true, but it says false which is wrong. Let me prove it replace first of p with character 's' now strings looks like : "mississippi" & "missisp." replace next of p with "si" now strings will be : "mississippi" & "mississip." replace next * of p with character 'p' now strings will be : "mississippi" & "mississipp." finally replace . of p with character 'i' final strings will be : "mississippi" & "mississippi"

Screenshots

Screenshot (56) Screenshot (57)

Additional context

No response

Winston Tang commented: Dear user,

Thank you for contacting us with your concern. We understand that encountering issues while solving problems might be frustrating.

However, after reviewing your concern, it appears to be a common point of confusion when starting to work with regular expressions. In the case of this problem, the * character indicates that the preceding character can occur zero or more times.

Therefore in your first reported test case, "ca" can indeed match "a" because the `` means that character 'c' can appear 0 times. And in the second case, "misisp." does not match "mississippi" because 's.' is trying to match 'ippi' but the given string has only one 's' before 'ippi'.

Regular expressions can be tricky to get used to but do keep trying! I recommend going back and thoroughly reviewing the problem's explanation and potentially seeking additional resources to become more familiar with regular expressions.

Don't hesitate to reach out if you have any further issues or concerns. Keep up with your hard work!

Best, LeetCode Support Team

LeetCode-Feedback / LeetCode-Feedback