Leetcode 10. Regular expression matching

s matn va p pattern berilgan. Matn içidan pattern böyiça mos kelişni tekşiruvçi funksiya yozing. Patternda '.' istalgan belgiga mos keladi, '*' özidan avvalgi belgining 0 yoki undan köp marta qaytarilişini tekşiradi.

Misol 1:

Input: s = "aa", p = "a" Output: false Tuşuntiriş: "a" pattern "aa" matn uçun mos emas.

Misol 2:**

Input: s = "aa", p = "a*" Output: true Tuşuntiriş:** '*' belgisi özidan avvalgi 'a' belgining bir neça marta qaytarilişini (yoki umuman bölmasligini) bildiradi.

Misol 3:**

Input: s = "ab", p = "." Output: true Tuşuntiriş:** "." istalgan belgining nol yoki undan köp marta qaytarilişini bildiradi ya'ni istalgan matnga mos keladi.

Işlaş tartibi

Agar şoşib turgan bölsangiz, şunçaki tayyor RegExp klassidan foydalaning. ;)

Aslida masalaning berilişi regex funksiyasini qölda yozişni talab qilinadi. Masalaga yondaşuvning birneça algoritmlari mavjud:

Masalani NFA simulyatsiyasi yordamida yeçiş bir soatdan köp vaqt olişi bois, Dynamic programming varianti bilan çeklanamiz.

Ikki ölçamli dp array yaratamiz. Uning siğimi [s.length() + 1][p.length() + 1] bölişi kerak, qöşimça bir qator va ustun bizga matn yoki pattern, yohud ikkalasi ham böş bölganida asqotadi.
Agar matn va pattern böş bölsa, dp[0][0] = true qaytaradi.
Arrayni töldirib bölganimizdan söng, dp[s.length()][p.length()] katakdagi qiymat funksiyaning yeçimi sifatida qaytariladi.

Misol uçun s = "aab" va p = "c*a*b" ni kö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

Birinçi ustun — p böş va u s ham böş bölgandagina mos keladi. Şu sababli dp[0][0] TRUE, qolgan dp[0][i] kataklariga FALSE töldiriladi.
Birinçi qator — qaysi p pattern böş s matnga mos kelişini belgilaydi. Böş matn uçun yoki böş pattern, yoki böş matnga ruxsat beruvçi a*, x*y* kabi patternlar töğri keladi. Yuqoridagi misolimizda, s matn böş bölganda va p = c* holatida, * borligi sababidan dp[0][2] = TRUE qiymat beriladi.
Böş bölmagan matnlar uçun agar s[i - 1] == p[j - 1] bölsa, demak i-1 çi va j-1 çi belgilar mos keladi, dp[i][j] = dp[i - 1][j - 1].
Agar p[j - 1] == ".", demak istalgan belgi mos keladi. Şuning uçun biz qolgan matnni ham tekşirib borişimiz kerak: dp[i][j] = dp[i - 1][j - 1].
Agar p[j - 1] == "*", demak yoki nol yoki undan köp belgili matnga mos keladi. Şu sababli dp[i][j] = dp[i][j - 2] yoki s[i - 1] == p[j - 2] || p[j - 2] == ".", tekşirilayotgan matndagi belgi patternda * oldidagi belgiga töğri keladi dp[i-1][j].

Tuşunarli bölişi uçun yana bir misolni kö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 böş bölgan holatida dp[0][0] = TRUE ga teng, çunki böş matn va böş 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

Böş pattern holatini töldirib çiqamiz. Matn bor bölsayu, pattern böş kelsa, u holda dp[0][i] = false böladi. Böş bölmagan matn böş 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

Böş string va böş bölmagan pattern holatini töldirib çiqamiz. Agar pattern c* yoki c*a* bölganda, böş matn patternga mos kelardi. Ammo bizning holatda xa*b.c böş matnga mos emas. Şuning uçun dp[j][0] qatordagi barça 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 tekşiramiz.

x : x. Belgi patterndagi belgiga mos keladi. Bu holda heç narsa özgarmagan, dp[1][1] ning qiymati dp[i - 1][j - 1] qiymatiga töğri keladi (oddiyroq aytganda, mos kelgan holat uçun diagonal yönalişda tepadagi dp[0][0] qiymati olinadi).

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

x : *. Bu holda * dan oldingi belgi 0 marta qaytarilişi mumkinligini hisobga olib, x ni ikkita oldingi ustundagi pattern qiymati bilan soliştiramiz. Agar ular mos kelsa, demak x : * taqqoslaş ham mos.

x : b. Mos emas.

x : . Mos keladi, bu holda dp[1][5] ning qiymati dp[0][4] qiymatiga töğri keladi (oddiyroq aytganda, mos kelgan holat uçun diagonal yönalişda 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 böyiça tekşiriş tugadi. Matndagi a belgisini tekşirişni boşlaymiz.

a : x. Mos emas.

a : a. Mos keladi. Bu holda diagonal böyiça bitta tepada turgan dp[1][1] ning qiymati olinadi. U - true

a : *. Bu holda * dan oldingi belgi 0 marta qaytarilişi mumkinligini hisobga olib, a ni ikkita oldingi ustundagi pattern qiymati bilan soliştiramiz. Ikkita oldingi ustunda x pattern bor, u a ga töğri kelmaydi. Endi * dan oldingi belgi bir marta qaytariliş ehtimolini hisobga olib tekşiramiz, ya'ni xa == xa*. a belgisi mos kelgani uçun 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 böyiça 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

Uçinçi belgi - a ni tekşirişni boşlaymiz.

a : x. Mos emas

a : a. Mos keladi. Diagonal böyiça bitta tepadagi qiymatni olamiz.

a : *. Bu holatda * dan oldingi belgi 0 marta qaytarilişi mumkinligini hisobga olib, a ni ikkita oldingi ustundagi pattern qiymati bilan soliştiramiz. Ikkita oldingi ustunda x pattern bor, u a ga töğri kelmaydi. Endi * dan oldingi belgi bir marta qaytariliş ehtimolini hisobga olib tekşiramiz, ya'ni xaa == xa*. a belgisi mos kelgani uçun 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 böyiça 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

Törtinçi belgi - b ni tekşirişni boşlaymiz.

b : x. Mos emas

b : a. Mos emas

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

b : b. Mos keladi. Diagonal böyiça bitta tepadagi qiymatni olamiz. U - true.

b : . Mos keladi. Diagonal böyiça 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

Beşinçi belgi - y ni tekşirişni boşlaymiz.

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 böyiça 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

Oltinçi belgi - c ni tekşirişni boşlaymiz.

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 böyiça bitta tepadagi qiymatni olamiz. U - false.

c : c. Mos keladi. Diagonal böyiça 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 sönggi katak - dp[6][6] ning qiymati true. Demak berilgan matn patternga mos keladi.

Masala - qiyin. Agar matnli tuşuntiriş yordam bermagan bölsa, uşbu videoni tavsiya qilaman:

WALKER

Leetcode 10. Regular expression matching

Işlaş tartibi

Kod