Regular expression matching

Kirish satri s va namuna p berilgan bo'lib, . va * belgilarini hisobga oluvchi regex tekshirgichni amalga oshiring:

• . (nuqta) har qanday bitta belgiga mos keladi.
• * (yulduzcha) undan oldingi belgining nol yoki undan ortiq marta uchrashiga mos keladi. Mos kelish satrning bir qismini emas, balki to'liq satrni qoplashi kerak.

func solve(s string, p string) bool {
    // ...
}

Misollar

Input: s = "aa", p = "a*"
Output: true
Tushuntirish: '*' belgisi 'a' ni qayta takrorlash imkonini beradi.

Input: s = "aa", p = "a"
Output: false

Input: s = "ab", p = ".*"
Output: true

Maslahatlar

1. Bu 2D dinamik dasturlash masalasi — dp[i][j] ni "s ning birinchi i ta belgisi p ning birinchi j ta belgisiga mos keladimi" deb ta'riflang, * belgisini alohida holat sifatida ko'rib chiqing.
2. Agar p[j-1] == '' bo'lsa, ikki variant mavjud: yulduzcha oldidagi belgini "nol marta" ishlatish (dp[i][j] = dp[i][j-2]) yoki agar p[j-2] joriy s[i-1] ga mos kelsa "yana bir marta" ishlatish (dp[i][j] = dp[i][j] || dp[i-1][j]). Aks holda, agar p[j-1] == '.' yoki p[j-1] == s[i-1] bo'lsa, dp[i][j] = dp[i-1][j-1]; bazaviy holatlarda dp[0][0]=true va dp[0][j] uchun p ning boshida "xy*..." kabi nolga moslashadigan shablonlarni to'g'ri hisoblang.