### Problem Statement

Given an input string (

`s`

) and a pattern (`p`

), implement wildcard pattern matching with support for `'?'`

and `'*'`

.'?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the

**entire**input string (not partial).**Note:**

`s`

could be empty and contains only lowercase letters`a-z`

.`p`

could be empty and contains only lowercase letters`a-z`

, and characters like`?`

or`*`

.

**Example 1:**

Input:s = "aa" p = "a"Output:falseExplanation:"a" does not match the entire string "aa".

**Example 2:**

Input:s = "aa" p = "*"Output:trueExplanation:'*' matches any sequence.

**Example 3:**

Input:s = "cb" p = "?a"Output:falseExplanation:'?' matches 'c', but the second letter is 'a', which does not match 'b'.

**Example 4:**

Input:s = "adceb" p = "*a*b"Output:trueExplanation:The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

**Example 5:**

Problem linkInput:s = "acdcb" p = "a*c?b"Output:false

### Video Tutorial

You can find the detailed video tutorial here### Thought Process

It seems an easy problem first using recursion and brute forcefully solving the problem, but the OJ will quickly throw a TLE (Time Limit Exceeded) error since it is exponential time. Well, if you were like me, tried really hard to optimize my brute force solution, either using some heuristics or pruning on the recursion, however, still no luck :(DP (Dynamic Programming) is normally a great way when trying to answer below two types of questions, and string related questions are a majority use case of DP

- Only Yes/No, True/False question without returning detailed step by step results
- Extreme values, e.g., Max, Min, Best optimal value

- Initialize your lookup array, could be 2 dimensional or 1 dimensional using rolling arrays
- Initialize the init values in your array
- Get the math formula for a[i] = a[i-1] * m - n or whatever condition you need
- Code it up

### Solutions

#### Brute force recursion, TLE

Time Complexity: assuming S length is M, P length is N, this is O(M*2^N), exponential basicallySpace Complexity: No extra space needed other than the additional recursion function stack

#### DP solution

Time Complexity: assuming S length is M, P length is N, this is O(M*N) because all we need to do is build up that lookup matrixSpace Complexity: assuming S length is M, P length is N, this is O(M*N), again, that lookup matrix

## No comments:

## Post a Comment

Thank your for your comment! Check out us at https://baozitraining.org/ if you need mock interviews!