The idea is to pre-process pattern string `p`

into characters with indication whether they are "fuzzy" match or not, which is to save all `'.'`

and alphabet characters of `p`

paired with a flag of "fuzzy" into `vector<pair<char, bool>> ps`

in the original order in `p`

. Note that **if we encounter a fuzzy match of type ".*", we can simply ignore any consecutive following fuzzy matches**. For example,

`p=".*a*.*f*bcd"`

is equivalent to `p=".*bcd"`

. However, any `"."`

cannot be ignored since each such pattern enforces the string length to be exact 1 character count.Then we will match characters in `s`

with `ps[i]`

one by one. Based on matching types, we have

**Non fuzzy match**: if current character in`s`

matches with`ps[i].first`

, continue to match next character with`ps[i+1].first`

; otherwise, cannot be matched.**Fuzzy match**: for any length between 0 and remaining length of unchecked`s`

, do non fuzzy type match with identical character`ps[i+1].first`

.

```
vector<pair<char, bool>> ps;
bool isMatch(string s, string p) {
for (auto i = p.begin(); i != p.end(); ++i) { // build ps[]
bool fuzzy_match = (i+1 != p.end() && *(i+1) == '*');
if (fuzzy_match && !ps.empty() && ps.back() == make_pair('.',true)) i++;
else ps.emplace_back(fuzzy_match? *i++:*i, fuzzy_match);
}
return dfs(s, 0);
}
bool dfs(const string& s, int i) {
if (i == ps.size()) return s.empty();
char c = ps[i].first;
if (!ps[i].second) // non fuzzy match
return (s.empty() || c != '.' && s[0] != c)? false : dfs(s.substr(1), i+1);
for (int j = 0; j <= s.length(); ++j) // fuzzy match
if (c != '.' && j && s[j-1] != c) return false;
else if (dfs(s.substr(j), i+1)) return true;
return false;
}
```