Optimize String Matching | Dataford Interview Questions

Optimize a naive recursive solution for string matching problems using memoization or bottom-up dynamic programming.

Implement is_match(text, pattern), where ? matches exactly one character and * matches zero or more characters. Matching must consume the entire input string and the entire pattern.

Input and Output

text and pattern are strings. Return True only when the complete strings match, otherwise return False.

Constraints

0 <= len(text) <= 2000
0 <= len(pattern) <= 2000
text contains lowercase English letters
pattern contains lowercase English letters, '?' and '*'
Matching is case-sensitive

Function Signature

def is_match(text, pattern):

Your question is Optimize String Matching. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem