There were two approaches that came to my mind when I first read this problem. This is a classic recursion problem and we can use a a modified DFS approach checking at each point if we can move left and down and then recurse from the new positions. The time complexity of this would be exponential of the order of …

## Leetcode – 10. Regular Expression Matching (Dynamic Programming)

This article is in continuation to my previous article solving the same problem with recursion. The fact that this problem could be solved with recursion made me think about the optimal substructure of this problem. As it turns out, this problem has one and can be solved using dynamic programming. To solve using dynamic programming, we will construct a table …

## Leetcode – 10. Regular Expression Matching

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 …