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.

1 2 3 |
if pattern.isEmpty { return string.isEmpty } |

Let’s talk implementation.

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

1 |
let firstMatch = !string.isEmpty && (string[0] == pattern[0] || pattern[0] == ".") |

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

## Comments 1

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