Leetcode 10. Regular expression matching

s matn va p pattern berilgan. Matn ichidan pattern bo’yicha mos kelishni tekshiruvchi funksiya yozing. Patternda '.' istalgan belgiga mos keladi, '*' o’zidan avvalgi belgining 0 yoki undan ko’p marta qaytarilishini tekshiradi.

Misol 1:

Input: s = "aa", p = "a"
Output: false
Tushuntirish: "a" pattern "aa" matn uchun mos emas.

Misol 2:

Input: s = "aa", p = "a*"
Output: true
Tushuntirish: '*' belgisi o'zidan avvalgi 'a' belgining bir necha marta qaytarilishini (yoki umuman bo'lmasligini) bildiradi.

Misol 3:

Input: s = "ab", p = ".*"
Output: true
Tushuntirish: ".*" istalgan belgining nol yoki undan ko'p marta qaytarilishini bildiradi ya'ni istalgan matnga mos keladi.

Ishlash tartibi

Agar shoshib turgan bo’lsangiz, shunchaki tayyor RegExp klassidan foydalaning. 😉

Aslida masalaning berilishi regex funksiyasini qo’lda yozishni talab qilinadi. Masalaga yondashuvning birnecha algoritmlari mavjud:

Masalani NFA simulyatsiyasi yordamida yechish bir soatdan ko’p vaqt olishi bois, Dynamic programming varianti bilan cheklanamiz.

Ikki o’lchamli dp array yaratamiz. Uning sig’imi [s.length() + 1][p.length() + 1] bo’lishi kerak, qo’shimcha bir qator va ustun bizga matn yoki pattern, yohud ikkalasi ham bo’sh bo’lganida asqotadi.
Agar matn va pattern bo’sh bo’lsa, dp[0][0] = true qaytaradi.
Arrayni to’ldirib bo’lganimizdan so’ng, dp[s.length()][p.length()] katakdagi qiymat funksiyaning yechimi sifatida qaytariladi.

Misol uchun s = "aab" va p = "c*a*b" ni ko’rib, undan DP jadvali yasaymiz.

			c	*	a	*	b
		0	1	2	3	4	5
	0	TRUE	FALSE	TRUE	FALSE	TRUE	FALSE
a	1	FALSE	FALSE	FALSE	TRUE	TRUE	FALSE
a	2	FALSE	FALSE	FALSE	FALSE	TRUE	FALSE
b	3	FALSE	FALSE	FALSE	FALSE	FALSE	TRUE

Birinchi ustun — p bo’sh va u s ham bo’sh bo’lgandagina mos keladi. Shu sababli dp[0][0] TRUE, qolgan dp[0][i] kataklariga FALSE to’ldiriladi.
Birinchi qator — qaysi p pattern bo’sh s matnga mos kelishini belgilaydi. Bo’sh matn uchun yoki bo’sh pattern, yoki bo’sh matnga ruxsat beruvchi a*, x*y* kabi patternlar to’g’ri keladi. Yuqoridagi misolimizda, s matn bo’sh bo’lganda va p = c* holatida, * borligi sababidan dp[0][2] = TRUE qiymat beriladi.
Bo’sh bo’lmagan matnlar uchun agar s[i - 1] == p[j - 1] bo’lsa, demak i-1 chi va j-1 chi belgilar mos keladi, dp[i][j] = dp[i - 1][j - 1].
Agar p[j - 1] == ".", demak istalgan belgi mos keladi. Shuning uchun biz qolgan matnni ham tekshirib borishimiz kerak: dp[i][j] = dp[i - 1][j - 1].
Agar p[j - 1] == "*", demak yoki nol yoki undan ko’p belgili matnga mos keladi. Shu sababli dp[i][j] = dp[i][j - 2] yoki s[i - 1] == p[j - 2] || p[j - 2] == ".", tekshirilayotgan matndagi belgi patternda * oldidagi belgiga to’g’ri keladi dp[i-1][j].

Tushunarli bo’lishi uchun yana bir misolni ko’rib, u asosida DP jadvali yaratamiz.

p = x*ab.c, s = xaabyc

			x	a	*	b	.	c
		0	1	2	3	4	5	6
	0
x	1
a	2
a	3
b	4
y	5
c	6

Matn va pattern bo’sh bo’lgan holatida dp[0][0] = TRUE ga teng, chunki bo’sh matn va bo’sh pattern bir biriga mos keladi.

			x	a	*	b	.	c
		0	1	2	3	4	5	6
	0	true
x	1
a	2
a	3
b	4
y	5
c	6

Bo’sh pattern holatini to’ldirib chiqamiz. Matn bor bo’lsayu, pattern bo’sh kelsa, u holda dp[0][i] = false bo’ladi. Bo’sh bo’lmagan matn bo’sh patternga mos kelmaydi.

			x	a	*	b	.	c
		0	1	2	3	4	5	6
	0	true
x	1	false
a	2	false
a	3	false
b	4	false
y	5	false
c	6	false

Bo’sh string va bo’sh bo’lmagan pattern holatini to’ldirib chiqamiz. Agar pattern c* yoki c*a* bo’lganda, bo’sh matn patternga mos kelardi. Ammo bizning holatda xa*b.c bo’sh matnga mos emas. Shuning uchun dp[j][0] qatordagi barcha kataklarga false kiritiladi.

			x	a	*	b	.	c
		0	1	2	3	4	5	6
	0	true	false	false	false	false	false	false
x	1	false
a	2	false
a	3	false
b	4	false
y	5	false
c	6	false

Matndagi x belgisini patternga tekshiramiz.

x : x. Belgi patterndagi belgiga mos keladi. Bu holda hech narsa o’zgarmagan, dp[1][1] ning qiymati dp[i - 1][j - 1] qiymatiga to’g’ri keladi (oddiyroq aytganda, mos kelgan holat uchun diagonal yo’nalishda tepadagi dp[0][0] qiymati olinadi).

x : a. Belgi patterndagi belgiga mos emas, katak qiymati false

x : *. Bu holda * dan oldingi belgi 0 marta qaytarilishi mumkinligini hisobga olib, x ni ikkita oldingi ustundagi pattern qiymati bilan solishtiramiz. Agar ular mos kelsa, demak x : * taqqoslash ham mos.

x : b. Mos emas.

x : . Mos keladi, bu holda dp[1][5] ning qiymati dp[0][4] qiymatiga to’g’ri keladi (oddiyroq aytganda, mos kelgan holat uchun diagonal yo’nalishda bitta tepadagi qiymat olinadi). U – false

x : c. Mos emas.

			x	a	*	b	.	c
		0	1	2	3	4	5	6
	0	true	false	false	false	false	false	false
x	1	false	*true*	false	true	false	false	false
a	2	false
a	3	false
b	4	false
y	5	false
c	6	false

x belgisi bo’yicha tekshirish tugadi. Matndagi a belgisini tekshirishni boshlaymiz.

a : x. Mos emas.

a : a. Mos keladi. Bu holda diagonal bo’yicha bitta tepada turgan dp[1][1] ning qiymati olinadi. U – true

a : *. Bu holda * dan oldingi belgi 0 marta qaytarilishi mumkinligini hisobga olib, a ni ikkita oldingi ustundagi pattern qiymati bilan solishtiramiz. Ikkita oldingi ustunda x pattern bor, u a ga to’g’ri kelmaydi. Endi * dan oldingi belgi bir marta qaytarilish ehtimolini hisobga olib tekshiramiz, ya’ni xa == xa*. a belgisi mos kelgani uchun bir qator tepadagi x == xa* qiymatini olamiz. dp[1][3] = true, demak dp[2][3] = true.

a : b. Mos emas.

a : . Mos keladi. Bu holda diagonal bo’yicha bitta tepada turgan dp[1][4] ning qiymati olinadi. U – false.

a : c. Mos emas.

			x	a	*	b	.	c
		0	1	2	3	4	5	6
	0	true	false	false	false	false	false	false
x	1	false	true	false	true	false	false	false
a	2	false	false	true	true	false	false	false
a	3	false
b	4	false
y	5	false
c	6	false

Uchinchi belgi – a ni tekshirishni boshlaymiz.

a : x. Mos emas

a : a. Mos keladi. Diagonal bo’yicha bitta tepadagi qiymatni olamiz.

a : *. Bu holatda * dan oldingi belgi 0 marta qaytarilishi mumkinligini hisobga olib, a ni ikkita oldingi ustundagi pattern qiymati bilan solishtiramiz. Ikkita oldingi ustunda x pattern bor, u a ga to’g’ri kelmaydi. Endi * dan oldingi belgi bir marta qaytarilish ehtimolini hisobga olib tekshiramiz, ya’ni xaa == xa*. a belgisi mos kelgani uchun bir qator tepadagi xa == xa* qiymatini olamiz. dp[2][3] = true, demak dp[3][3] = true.

a : b. Mos emas

a : . Mos keladi. Bu holda diagonal bo’yicha bitta tepada turgan dp[2][4] ning qiymati olinadi. U – false.

a : c. Mos emas.

			x	a	*	b	.	c
		0	1	2	3	4	5	6
	0	true	false	false	false	false	false	false
x	1	false	true	false	true	false	false	false
a	2	false	false	true	true	false	false	false
a	3	false	false	false	true	false	false	false
b	4	false
y	5	false
c	6	false

To’rtinchi belgi – b ni tekshirishni boshlaymiz.

b : x. Mos emas

b : a. Mos emas

b : *. * dan oldingi pattern belgisi – a. U b ga mos emas.

b : b. Mos keladi. Diagonal bo’yicha bitta tepadagi qiymatni olamiz. U – true.

b : . Mos keladi. Diagonal bo’yicha bitta tepadagi qiymatni olamiz. U – false.

b : c. Mos emas.

			x	a	*	b	.	c
		0	1	2	3	4	5	6
	0	true	false	false	false	false	false	false
x	1	false	true	false	true	false	false	false
a	2	false	false	true	true	false	false	false
a	3	false	false	false	true	false	false	false
b	4	false	false	false	false	true	false	false
y	5	false
c	6	false

Beshinchi belgi – y ni tekshirishni boshlaymiz.

y : x. Mos emas

y : a. Mos emas

y : *. * dan oldingi pattern belgisi – a. U y ga mos emas.

y : b. Mos emas.

y : . Mos keladi. Diagonal bo’yicha bitta tepadagi qiymatni olamiz. U – true.

y : c. Mos emas.

			x	a	*	b	.	c
		0	1	2	3	4	5	6
	0	true	false	false	false	false	false	false
x	1	false	true	false	true	false	false	false
a	2	false	false	true	true	false	false	false
a	3	false	false	false	true	false	false	false
b	4	false	false	false	false	true	false	false
y	5	false	false	false	false	false	true	false
c	6	false

Oltinchi belgi – c ni tekshirishni boshlaymiz.

c : x. Mos emas

c : a. Mos emas

c : *. * dan oldingi pattern belgisi – a. U c ga mos emas.

c : b. Mos emas.

c : . Mos keladi. Diagonal bo’yicha bitta tepadagi qiymatni olamiz. U – false.

c : c. Mos keladi. Diagonal bo’yicha bitta tepadagi qiymatni olamiz. U – true.

			x	a	*	b	.	c
		0	1	2	3	4	5	6
	0	true	false	false	false	false	false	false
x	1	false	true	false	true	false	false	false
a	2	false	false	true	true	false	false	false
a	3	false	false	false	true	false	false	false
b	4	false	false	false	false	true	false	false
y	5	false	false	false	false	false	true	false
c	6	false	false	false	false	false	false	true

Eng so’nggi katak – dp[6][6] ning qiymati true. Demak berilgan matn patternga mos keladi.

Masala – qiyin. Agar matnli tushuntirish yordam bermagan bo’lsa, ushbu videoni tavsiya qilaman:

Ishlash tartibi

Kod