Match an Entire String with Dot and Star
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Determine whether the pattern `pattern` matches all of the string `text`. Return a boolean result.
A pattern element is either a lowercase English letter or a dot (`.`). A letter matches itself, while a dot matches exactly one character. An element followed by a star (`*`) can match zero or more consecutive occurrences of that element. The star modifies the preceding element; it is not an independent wildcard.
The complete pattern must account for every character in `text`. A match that covers only a prefix or another part of the string is insufficient.
### Examples
**Example 1**
```text
Input: text = "bbbc", pattern = "a*b*c"
Output: true
```
Here `a*` matches no characters, `b*` matches the three `b` characters, and the final `c` matches itself. Together they cover the entire string.
**Example 2**
```text
Input: text = "hjk", pattern = ".*j"
Output: false
```
A full match with this pattern would have to finish with `j`, but the string ends with `k`.
### Constraints
- `1 <= text.length <= 20`
- `1 <= pattern.length <= 20`
- Every character in `text` is a lowercase English letter.
- Characters in `pattern` are lowercase English letters, `.` or `*`.
- Every `*` has a valid preceding element to repeat.
Overview: Match a complete string against a pattern containing lowercase letters, dot and star, including zero repetitions and strict full-string matching.
Community answers
Answer by Coderka14
#include
using namespace std;
class Solution {
public:
vector> dp;
bool solve(int i, int j, string& text, string& pattern) {
if (dp[i][j] != -1) {
return dp[i][j];
}
if (j == pattern.size()) {
return dp[i][j] = (i == text.size());
}
bool match = (i < text.size() && (text[i] == pattern[j] || pattern[j] == '.'));
bool result;
if (j + 1 < pattern.size() && pattern[j + 1] == '*')
{
result = solve(i, j + 2, text, pattern) || (match && solve(i + 1, j, text, pattern));
}
else
{
result = match && solve(i + 1, j + 1, text, pattern);
}
return dp[i][j] = result;
}
bool isMatch(string text, string pattern) {
int n = text.size();
int m = pattern.size();
dp.assign(n + 1, vector(m + 1, -1));
return solve(0, 0, text, pattern);
}
};
/*
Approach: Recursion + Memoization
Use the same recursive choices as brute force.
dp[i][j] stores whether text[i...] matches pattern[j...].
If a state has already been computed, return its stored result.
Otherwise, compute the result and save it.
Time Complexity: O(n * m)
Auxiliary Space: O(n * m) for memoization and recursion stack.
*/