WALKER

Dasturchi, frilanser, gik va introvert

by Sherzod Shermukhamedov

Leetcode 5. Longest Palindromic Substring

Bizga s string berilgan. Undan eng uzun palindrom substringni topiş kerak. s string uzunligi 1 va 1000 belgi orasida böladi.

Misol:

Input: s = "babad" Output: "bab" Tuşuntiriş: "aba" ham töğri javob.

Palindrom deb, öng va çap qismi bir-biriga simmetrik bölgan sözlarga aytiladi. Ya'ni sözni ohiridan boşiga öqiganda ham bir xil söz çiqadi. Masalan:

aziza, amma, kiyik, kallak, tabobat, ...

Ba'zi sözlarning qismida esa palindrom mavjud: ananas, baobab, ...

Işlaş tartibi

Masalani işlaşning turliça - bruteforce, dynamic programming, expand around center usullari mavjud. Biz qisqaroq bölgani uçun expand around center algoritmini körib ötamiz.

Har bir palindrom aslida markazida bitta yoki ikkita harf joylaşgan oynali söz. Masalan "anana" sözida örtadagi a harfi - markaz, abba sözida esa markaz - bb. Bu faktni hisobga olgan holda, markazdan boşlab tekşirib çiquvçi funksiya yoziş mumkin.

Dastlab, sikl içida sözning har bir harfini markazligiga tekşiramiz.

  1. banana. b - markaz, uning çap tarafida harf yöq, demak maksimum palindrom "b"ga teng.
  2. banana. a - markaz, uning çap tarafida b, öng tarafida n mavjud, demak ban palindrom emas, a ning özi palindrom. Bizda eng uzun palindrom b bölib turgani uçun, uning özini qoldiramiz.
  3. banana. n - markaz, uning çap va öng tarafida bir xil - a harfi bor. Hozirça bizda ana palindromi hosil böldi. Tekşirişni çap va öng tarafga davom ettiramiz. Bu safar banan - palindrom emas. Demak hozir bizda banana sözida ana palindromi topildi.
  4. banana. a - markaz. uning çap va öng tarafida bir xil - n harfi bor. Hozirça bizda nan palindromi hosil böldi. Tekşirişni çap va öng tarafga davom ettiramiz va anana palindromini topamiz. Çap va öngga yana kengaytira olmaymiz, sababi çapda b harfi bölsa, öng tarafi böş qoldi. Demak hozir bizda banana sözida anana palindromi topildi. anana palindromi ana palindromidan uzunroq bölgani uçun bizda maksimum palindrom hozirça anana.
  5. banana. n - markaz. Çap va öng tarafida bir xil - a harfi bor. Hozirça bizda ana palindromi hosil böldi. Tekşirişni çap va öng tarafga davom ettira olmaymiz, çunki ana ning öng tarafida harf yöq. ana palindromi anana dan kalta bölgani uçun anana palindromi eng uzunligiça qoladi.
  6. banana. a - markaz. Öng tarafida harf yöq. Palindrom a ga teng. U anana palindromidan kalta, şu sababli eng uzun palindrom - anana ligiça qoladi.

Yuqoridagi kodning muammosi şundaki, u markazi ikki harfli palindromlarni topmaydi. Masalan sabbad sözida palindrom abba bölsa ham, kod s ni palindrom sifatida qaytaradi.

Kodni optimizatsiya qilib quyidagiça körinişga olib kelamiz: