Regular Expression Matching
Hard · Dynamic Programming · about 35 minutes
Asked at Google, Meta, Amazon, Microsoft, Bloomberg, Airbnb, Yelp.
Write a matcher for a small pattern language with two special characters: '.' stands for any one character, and '*' lets the character just before it repeat any number of times, including zero. Return true only if the pattern p accounts for the whole string s. Every '*' in p comes right after a letter or a '.'.