Practice/Amazon/Leetcode 10. Regular Expression Matching

Leetcode 10. Regular Expression Matching

CodingOptional

Problem

You are given a text string and a pattern string. Implement a function that determines whether the pattern matches the entire text string.

The pattern may contain two special characters:

• . (dot) — matches any single character
• * (asterisk) — matches zero or more of the immediately preceding character

The matching must cover the entire text string, not just a portion of it.

Requirements

1. Return true if the pattern matches the entire text, otherwise return false
2. The * operator applies to the character immediately before it
3. The . character can match any single character including letters, digits, and symbols
4. The * can be applied to . as well (e.g., .* matches zero or more of any character)
5. An empty pattern only matches an empty text

Constraints

• 0 ≤ text.length ≤ 20
• 0 ≤ pattern.length ≤ 30
• text contains only lowercase English letters
• pattern contains only lowercase English letters, ., and *
• It is guaranteed that * always has a preceding character
• Target time complexity: O(m × n) where m = text.length and n = pattern.length
• Target space complexity: O(m × n)

Examples

Example 1:

Input: text = "aa", pattern = "a" Output: false Explanation: The pattern "a" only matches one character, but the text has two characters.

Example 2:

Input: text = "aa", pattern = "a*" Output: true Explanation: The "a*" pattern matches two 'a' characters (one or more occurrences).

Example 3:

Input: text = "ab", pattern = ".*" Output: true Explanation: The ".*" pattern matches any sequence of characters, including "ab".

Example 4:

Input: text = "aab", pattern = "c*a*b" Output: true Explanation: "c*" matches zero 'c's, "a*" matches two 'a's, and "b" matches 'b'.