DiffPush Tier Dynamic Programming · DP on Strings O(n*m) · O(m)
A security appliance matches access-log lines against admin-supplied filters. A filter may contain '?' standing for exactly one arbitrary character and '*' standing for any run of characters — including none. The whole line must satisfy the filter, not just a fragment. The matching engine decides, for every (line, filter) pair, whether the pattern covers the line end to end.
Input: A string s (the log line) and a pattern p containing letters, '?', and '*'.
Output: Return true when p matches the entirety of s under the wildcard rules, otherwise false.
0 <= len(s), len(p) <= 2000s contains only lowercase English lettersp contains lowercase English letters, '?', and '*'Input: {"s":"aa","p":"a"}
Output: false
A lone 'a' cannot cover two characters.
Input: {"s":"aa","p":"*"}
Output: true
'*' absorbs the whole line, including the empty run.