Implement Regular Expression Matching
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
# Implement Regular Expression Matching
Determine whether an entire input string matches a pattern containing lowercase letters and two special symbols:
- `.` matches any single character.
- `*` matches zero or more occurrences of the immediately preceding letter or `.`.
### Function Signature
```python
def is_full_match(text: str, pattern: str) -> bool:
...
```
### Examples
```text
Input: text = "aa", pattern = "a"
Output: false
Input: text = "aa", pattern = "a*"
Output: true
Input: text = "ab", pattern = ".*"
Output: true
Input: text = "aab", pattern = "c*a*b"
Output: true
```
### Constraints
- `0 <= len(text), len(pattern) <= 2_000`
- `text` contains only lowercase English letters.
- `pattern` contains lowercase English letters, `.`, and `*`.
- The pattern is well formed: `*` is never first and never immediately follows another `*`.
### Clarifications
- Matching must consume the entire text and entire pattern; it is not substring search.
- `*` applies only to the one token immediately before it.
- An empty text can match a pattern such as `"a*b*"`.
- Return a primitive Boolean and do not mutate either input.
- The `.`/`*` language is an explicit practice assumption because the source names regex matching without restating its grammar.
### Hints
- A state can represent how much of the text and pattern have already been matched.
- At a starred token, consider both using zero copies and consuming one matching text character.
Quick Answer: Implement full-string regular expression matching for lowercase letters, dot wildcards, and star repetition. Handle empty strings and zero-copy star cases with dynamic programming while keeping the pattern grammar and whole-input semantics precise.
Return whether an entire lowercase text matches a pattern containing literals, dot for one character, and star for zero or more copies of the preceding token.
Constraints
- Text and pattern lengths are at most 2000
- Star is never first or consecutive
- Matching must consume both inputs completely
Examples
Input: {'text': 'aa', 'pattern': 'a'}
Expected Output: False
Explanation: One literal cannot consume two characters.
Input: {'text': 'aa', 'pattern': 'a*'}
Expected Output: True
Explanation: The star consumes two a characters.
Hints
- Let a state represent prefixes of the text and pattern.
- At a star, either skip its token-star pair or consume one matching text character while staying at the star.