Leetcode – 10. Regular Expression Matching

Reading Time: 2 minutes

My initial thought after reading the description of this problem is that let’s just consider, for the moment, that this problem needs to be implemented for only. For e.g given the text abc does it match a•b? You can come up with examples and you will realize that to implement just the , the lengths of the two strings have to be equal.

So the problem to solve just for is really trivial as you can initially check if the lengths are the same and just bomb out if they’re not and if the lengths are equal, just iterate over the two strings character by character and check if there is a match.

Let’s talk about the base case.

Does a string match an empty pattern? Yes, iff the string is empty.

Let’s talk implementation.

If the text is not empty, we can check to see if the first characters match.

This is very crucial for two reasons:

  • It determines how the program proceeds in the event that that there is a * at index 1. If there is a * at index 1, it is important to move the string pointer ahead and keep the pattern pointer where it is. For example, given aa and a*, firstMatch would be true and now we have to determine if the substring a matches a*
  • If the above condition isn’t true, that means we are either checking for a or a direct match. In which case, it only makes sense to proceed iff firstMatch is true.

Consider string = aab and pattern = a*b. We have a firstMatch, but as the pattern has a * at index 1, means one of two things could be true

  • Advance the text pointer forward and check to see if ab matches the pattern a*b (Recursively, turns out to be true as firstMatch is true)

OR

  • Advance the pattern pointer by 2 and check to see if aab matches the pattern b (Independent of the value of firstMatch)

Consider text=abbc and pattern = a•*c. Just as above, we have a firstMatch but the pattern has a at index 1, so we move out text and pattern pointers forward by 1 and check to see if bbc matches •*c and go on recursively…

Time Complexity: If solving only for , the time complexity would be O(N) on the length of the shorter of the two strings. Calculating the complexity becomes challenging when considering both wild card characters and there is an explanation on how to derive it on Leetcode.

Space Complexity: Again, a lot of extra String instances are created from Substring instances just because the way Swift handles the two types and therefore, the space complexity would be approximately equal to the time complexity as explained on Leetcode.

The problem is taken from Leetcode

Solution hosted on Github

Mohit AthwaniLeetcode – 10. Regular Expression Matching

Comments 1

  1. Pingback: Leetcode – 10. Regular Expression Matching (Dynamic Programming) | Mohit Athwani

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.