Longest Common Prefix - LeetCode

Muammoning quyilishi : Sizga bir nechta satrlar berilgan. Shu satrlarning eng uzun umumiy prefixini topuvchi funksiya tuzing.

Kiruvchi ma'lumot: strs-satrlar ruyxati

Chiquvchi ma'lumot: eng uzun umumiy prefix.

Follow up: Xush siz muammoni O(N^2) kamroq asimptotikada (tezlikda) ishlaydigan algoritmda tuza olaszmi?

Chegaralar:

1<=|satrlar soni|<=200

0<=|har bir satrdagi belgilar soni|<=200

Barcha belgilar faqat kichik lotin alifbosida berilgan.

Yechim:

Masalani yechimini keltirishdan oldin bazi asosiy tushunchalarni mohiyatiga yetishga harakat qilamiz.

Formal ma'noda prefix bu -satrning 0-indexidan boshlab qaysidir i-(i=0..|s|) gacha qismi hisoblanadi.

Agar satrlarda umumiy prefix mavjud bo'lsa uning uzunligi hech qachon eng kichik satrning uzunligidan oshmaydi.!!

Birinchi satrni "Algorithm" tayanch satr sifatida qabul qilib uning har bir elementini qolgan satrlarda mavjudligini tekshiramiz.

Algoritmning umumiy asimptotikasi : O(N^2)

Memory Complexity : O(N)

Bunda N-satrlar soni.