p = ?u*t*n
s = button

Рассмотрим префиксы:
?u  нет        ?|u да
but            b|u 
Последний символ шаблона:
  1. буква => такая же буква должна быть в строке последней
     f (i, j) = f (i - 1, j - 1) AND (p[i] == s[j])
  2. ? => съедаем последнюю букву строки
     f (i, j) = f (i - 1, j - 1)
  3. * => съедаем любое количество последних букв строки
     f (i, j) = OR f (i - 1, 0 <= x <= j)
     f (i, j) = f (i - 1, j) OR f (i, j - 1)

В терминах задачи:
"разменять * на подстроку"
разобьём на элементарные операции
  * удалить последний символ строки
  * удалить * (последняя операция)