I’ve seen this problem more than a year ago and back then I kinda memorized the solution.

This time, I tried to solve the problem myself and got nearly 2/3rd of the pseudo code.

There’s 3 cases to this problem:

- 1. If
`s[sI] == p[pI] || p[pI] == '.'`

, simply recurse with`sI + 1`

and`pI + 1`

- 2. If
`pI + 1 == '*'`

, then:- 2.1. Try to match
`s`

with`p[pI + 2 ...]`

- 2.2. If above fails, check the condition in
*1*is satisfied, if yes, recurse with`sI + 1`

and`pI`

. This solves cases like`s = aa`

and`p = a*`

- 2.1. Try to match

I was able to get *1* and *2.1* by myself.

**Tip:** Solve case *2* before *1* in code.

The time complexity is `O(N)`

where `N`

is the longer of the 2 strings.

The space complexity is `O(N)`

where `N`

is the longer of the 2 strings..

The problem is taken from Leetcode.

Solution is hosted on Github.