This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Implement regular expression matching with support for `'.'`

and `'*'`

.

'.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover theentireinput string (not partial). The function prototype should be: bool isMatch(const char *s, const char *p) Some examples: isMatch("aa","a") → false isMatch("aa","aa") → true isMatch("aaa","aa") → false isMatch("aa", "a*") → true isMatch("aa", ".*") → true isMatch("ab", ".*") → true isMatch("aab", "c*a*b") → true

b'

\n## Solution

\n

\n#### Approach #1: Recursion [Accepted]

\n

\n#### Approach #2: Dynamic Programming [Accepted]

\n

\n

'
\n\n

\n\n

**Intuition**

If there were no Kleene stars (the `*`

wildcard character for regular expressions), the problem would be easier - we simply check from left to right if each character of the text matches the pattern.

When a star is present, we may need to check many different suffixes of the text and see if they match the rest of the pattern. A recursive solution is a straightforward way to represent this relationship.

\n**Algorithm**

Without a Kleene star, our solution would look like this:

\n\nIf a star is present in the pattern, it will be in the second position . Then, we may ignore this part of the pattern, or delete a matching character in the text. If we have a match on the remaining strings after any of these operations, then the initial inputs matched.

\n\n\n**Complexity Analysis**

- \n
- \n
Time Complexity: Let be the lengths of the text and the pattern respectively. In the worst case, a call to

\n`match(text[i:], pattern[2j:])`

will be made times, and strings of the order and will be made. Thus, the complexity has the order . With some effort outside the scope of this article, we can show this is bounded by . \n - \n
Space Complexity: For every call to

\n`match`

, we will create those strings as described above, possibly creating duplicates. If memory is not freed, this will also take a total of space, even though there are only order unique suffixes of and that are actually required. \n

\n

**Intuition**

As the problem has an **optimal substructure**, it is natural to cache intermediate results. We ask the question : does and match? We can describe our answer in terms of answers to questions involving smaller strings.

**Algorithm**

We proceed with the same recursion as in Approach #1, except because calls will only ever be made to `match(text[i:], pattern[j:])`

, we use to handle those calls instead, saving us expensive string-building operations and allowing us to cache the intermediate results.

*Top-Down Variation*\n

*Bottom-Up Variation*

**Complexity Analysis**

- \n
- \n
Time Complexity: Let be the lengths of the text and the pattern respectively. The work for every call to

\n`dp(i, j)`

for ; is done once, and it is work. Hence, the time complexity is . \n - \n
Space Complexity: The only memory we use is the boolean entries in our cache. Hence, the space complexity is .

\n \n

\n

Analysis written by: @awice

\n