Pattern Text Matching

HARD40 pts

You are given a text string s and a pattern string p. Your task is to implement a pattern matching engine that determines whether the pattern fully matches the entire text string. The pattern may contain two special metacharacters:

'.' (dot): Acts as a wildcard that matches exactly one occurrence of any single character from the text.
'*' (asterisk): A quantifier that applies to the character immediately preceding it, allowing that character to appear zero or more times in succession.

The goal is to return true if the pattern can describe the complete text string from start to finish, and false otherwise. Unlike partial matching, the pattern must account for every character in the text—no leftover or unmatched portions are allowed.

Key Observations:

The asterisk '*' never appears as the first character in the pattern, and it always has a valid preceding character to quantify.
The dot '.' combined with '' (i.e., '.') creates a powerful construct that can match any sequence of zero or more characters, essentially acting as a universal wildcard.
Matching decisions often depend on future characters in both strings, making this a classic candidate for dynamic programming or memoized recursion.

Example

Input

s = "aa"
p = "a"

Output

false

Explanation

The pattern 'a' represents exactly one 'a' character. Since the text 'aa' contains two 'a' characters, the pattern cannot cover the entire string. The matching fails because there's an extra 'a' left unmatched.

Example

Input

s = "aa"
p = "a*"

Output

true

Explanation

The '' quantifier allows the preceding 'a' to repeat zero or more times. By using the '' to repeat 'a' twice, the pattern 'a*' successfully matches the entire text 'aa'. This demonstrates the power of the Kleene star operator.

Example

Input

s = "ab"
p = ".*"

Output

true

Explanation

The pattern '.' combines the wildcard '.' with the asterisk ''. The '.' matches any single character, and '' allows it to repeat any number of times. Together, '.' matches any string of any length, including 'ab'. This is the most permissive pattern possible.

Accepted0/0·0% Acceptance

Constraints

1 ≤ s.length ≤ 20
1 ≤ p.length ≤ 20
s contains only lowercase English letters (a-z).
p contains only lowercase English letters (a-z), '.', and '*'.
For every '*' in p, there is a valid preceding character to which it applies.

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

p =

"a"

s =

"aa"

Pattern Text Matching

Hints

Pattern Text Matching

Hints