A pattern p describes a family of strings. Besides ordinary letters, which must appear exactly as written, it can hold two special characters:
. stands for any one character.* means the character just before it, repeated any number of times, including zero. So b* matches the empty string, b, bb, bbb, and so on, and .* matches any string at all.Return true if the pattern matches the whole string s, and false otherwise. Matching only part of s is not enough.
h matches h, . matches e, l* matches ll (two repeats), and o matches o.
z* covers zz, but nothing in the pattern can match the final x, and the match has to reach the end of s.
b* can repeat b zero times, so the pattern also matches ac.
Constraints
1 <= s.length <= 201 <= p.length <= 20s contains only lowercase English letters.p contains only lowercase English letters, . and *.* in p comes right after a letter or a ., never at the start and never after another *.Whether the rest of s matches the rest of p depends only on two positions, i in s and j in p. Backtracking reaches the same (i, j) pair again and again, so remember each answer.
true