Question:
Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:
- '.' Matches any single character.
- '*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Example 1:
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:
Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Answer:
The problem can be solved using dynamic programming. We can create a 2D table where memory[i][j] represents whether the substring of s starting from index i and the pattern p starting from index j match.
Approach:
1. Initialization:
- We initialize a 2D array memory with dimensions (len(s) + 1) x (len(p) + 1). This is done to handle the case where either s or p is empty.
- We set memory[len(s)][len(p)] to True because an empty substring of s and an empty pattern p match.
2. Iteration:
- We iterate through the substrings of s and patterns p from the end towards the beginning using two nested loops.
- For each index i and j, we check if the current characters match or if the pattern character is '.'. This is indicated by the variable match.
- If the next character in the pattern is '*', we handle the '*' wildcard character by exploring both options: matching zero occurrences and matching the current character. This is achieved by updating the memory[i][j] value accordingly.
- If the next character is not '*', we simply check if the current characters match and update the memory[i][j] value accordingly.
3. Return:
- After the iteration is complete, we return memory[0][0], which represents whether the entire s matches the entire p.
The overall approach is dynamic programming, where we fill the memory table iteratively based on previously computed values. We utilize this table to store intermediate results of subproblems, which helps in avoiding redundant computations and improves the efficiency of the solution. The iteration is done from the end towards the beginning to ensure that we have access to the necessary subproblem solutions when computing the current cell values.
Time complexity:
(O(m * n)), where (m) is the length of string s and (n) is the length of pattern p. We iterate through each cell in the memory table once.
Space complexity:
(O(m * n)), where (m) is the length of string s and (n) is the length of pattern p. We use a 2D array memory to store the results of subproblems. Each cell in the table requires constant space.
Code:
class Solution:
def isMatch(self, s: str, p: str) -> bool:
# Initialize a 2D array `memory` with dimensions (len(s) + 1) x (len(p) + 1)
memory = [[False] * (len(p) + 1) for i in range(len(s) + 1)]
# Set memory[len(s)][len(p)] to True since an empty substring of s and an empty pattern p match
memory[len(s)][len(p)] = True
# Iterate through the substrings of s and patterns p from the end towards the beginning
for i in range(len(s), -1, -1):
for j in range(len(p) - 1, -1, -1):
# Check if the current characters match or if the pattern character is '.'
match = i < len(s) and (s[i] == p[j] or p[j] == ".")
if (j + 1) < len(p) and p[j + 1] == "*":
# If the next character in the pattern is '*', handle the '*' wildcard character
memory[i][j] = memory[i][j + 2]
if match:
memory[i][j] = memory[i + 1][j] or memory[i][j]
elif match:
# If the characters match, move to the next characters in both strings
memory[i][j] = memory[i + 1][j + 1]
# Return memory[0][0], which represents whether the entire s matches the entire p
return memory[0][0]
.png)
.png)
.png)
.png)
0 Comments