Leetcode 10: Regular Expression Matching

The Kleene stars (the * wildcard character for regular expressions) make this difficult. We can’t just gobble up all the wildcard matching characters, otherwise subsequent matches might not work. One way to solve this is by recursing every possibility, so if we have p=“.*abc” and s=“xyzabcabc” then we call our match function with offsets match(s,p,0,2) then match(s,p,1,2) then match(s,p,2,2), etc.. until we have a complete match for the rest of the string. Note that once we’ve read all of string s then we need to step over any trailing wildcards, which don’t need any characters to match.

We can speed this up by using Dynamic Programming memoization to cache previous results. I have included the code for this below the non-memoized embedded code below.

DP solution: https://gist.github.com/adamkorg/67f7f5bd9eb1c8ae73f1e55c1d54d1b9

This entry was posted in programming and tagged , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *