REGEX MATCHING HARD
problema
Dada uma string s e um padrão p, diga se o padrão casa com a string. O padrão
suporta dois caracteres especiais:
· . casa com qualquer caractere (exatamente um).
· * casa com zero ou mais repetições do elemento imediatamente antes dele.
O casamento precisa cobrir a string inteira, não só um pedaço dela.
Exemplo 1 ·
s = "aa", p = "a" → false
"a" casa com um caractere só, e sobra um "a".
Exemplo 2 ·
s = "aa", p = "a*" → true
"a*" repete o "a" duas vezes.
Exemplo 3 ·
s = "ab", p = ".*" → true
".*" é "zero ou mais de qualquer caractere", então cobre "ab".
Restrições: 1 ≤ s.length ≤ 20 · 1 ≤ p.length ≤ 20 · s só tem letras minúsculas · p tem letras minúsculas, '.' e '*' · todo '*' vem depois de um caractere válido