Standard Simplified RegEx Implementation

Although this problem constraints the regex to one "*", it is simple to extend the solution to multiple stars. Two important points to consider here:

1. Instead of doing string manipulation, just pass and manipulate indexes

2. Think about the base case and the induction case

Time seems to be a higher side due to the recursion and extrapolation to handling multiple stars. Code is down below, cheers, ACC.

Substring Matching Pattern - LeetCode

You are given a string s and a pattern string p, where p contains exactly one '*' character.

The '*' in p can be replaced with any sequence of zero or more characters.

Return true if p can be made a 

substring

 of s, and false otherwise.

 

Example 1:

Input: s = "leetcode", p = "ee*e"

Output: true

Explanation:

By replacing the '*' with "tcod", the substring "eetcode" matches the pattern.

Example 2:

Input: s = "car", p = "c*v"

Output: false

Explanation:

There is no substring matching the pattern.

Example 3:

Input: s = "luck", p = "u*"

Output: true

Explanation:

The substrings "u", "uc", and "uck" match the pattern.

 

Constraints:

• 1 <= s.length <= 50
• 1 <= p.length <= 50
• s contains only lowercase English letters.
• p contains only lowercase English letters and exactly one '*'

---

Seen this question in a real interview before?

1/5

Yes

No

Accepted

20.6K

Submissions

86.1K

Acceptance Rate

23.9%

public bool HasMatch(string s, string p)
{
    //N^2, but N = 50
    for (int start = 0; start < s.Length; start++)
    {
        for (int end = start; end < s.Length; end++)
        {
            if (HasMatch(s, p, end, start, 0))
                return true;
        }
    }

    return false;
}

private bool HasMatch(string str,
                        string regex,
                        int strEndIndex,
                        int strCurrentIndex,
                        int regexCurrentIndex)
{
    //Base
    if (strCurrentIndex > strEndIndex || regexCurrentIndex >= regex.Length)
    {
        for (int i = regexCurrentIndex; i < regex.Length; i++)
        {
            if (regex[i] != '*')
                return false;
        }
        return true;
    }

    //Induction
    if (regex[regexCurrentIndex] == '*')
    {
        for (int i = strCurrentIndex; i <= strEndIndex; i++)
        {
            if (HasMatch(str, regex, strEndIndex, i, regexCurrentIndex + 1))
                return true;
        }
        return false;
    }
    else
    {
        if (str[strCurrentIndex] != regex[regexCurrentIndex])
            return false;
        return HasMatch(str, regex, strEndIndex, strCurrentIndex + 1, regexCurrentIndex + 1);
    }
}