Leetcode Problem 10. Regular Expression Matching

10. Regular Expression Matching

Leetcode Solutions

Dynamic Programming Approach

  1. Initialize a 2D boolean array dp with dimensions (len(s) + 1) x (len(p) + 1).
  2. Set dp[0][0] to True to represent that an empty string matches an empty pattern.
  3. Handle patterns that start with '*' by setting dp[0][j] to True if dp[0][j-2] is True.
  4. Iterate over each character in s and p using indices i and j.
  5. If p[j-1] is '.' or s[i-1] == p[j-1], set dp[i][j] to the value of dp[i-1][j-1].
  6. If p[j-1] is '*', check two conditions: a. If the pattern before '*' matches zero occurrences, set dp[i][j] to dp[i][j-2]. b. If the pattern before '*' matches one or more occurrences, set dp[i][j] to dp[i-1][j] if s[i-1] matches p[j-2].
  7. The answer is the value at dp[len(s)][len(p)].
UML Thumbnail

Recursive Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...