Valid parentheses (To'g'ri qavslar)
Bu masalani ko'pchiligimiz ishlaganmiz. LeetCodedagi "easy" masalalardan.
Masalan shunday string'lar berilganda funksiyamiz true/false qaytarishi kerak. String lar faqat "(" va ")" qavslaridan iborat.
"" // true
"()" // true
"(())" // true
"()()(())" // true
"())" // false
")()" // false
Intervyuda tushgan masala 2 qismdan iborat edi:
1. Check validity of input string.
2. Return valid string of parentheses.
You can delete, insert, flip a character. Return option with minimum number of edits!
1-qism oddiy, stack bilan ishlanadi. Tushuntirib o'tirmayman. Shunchaki o'zingiz ishlab ko'ring 😉
2-qism... uxxx... . Yaxshigina boshimni qotirib qo'ydi.
Demak, qavslarimiz to'g'ri bo'lsa stringni o'zini qaytaramiz. Agar noto'g'ri bo'lsa, to'g'rilab qaytaramiz.
Ya'ni har qanday holatda funksiyamizdan to'g'ri qavslardan iborat string qaytishi shart!
Eslataman, stringni to'g'rilash uchun 3 ta amal bajarish mumkin:
1. delete - o'chirish
2. flip - teskari o'girish
3. insert - qavs kiritish (ochuvchi yoki yopuvchi)
Xullas, misol keltiraman:
input = "()"
output = "()" // to'g'ri bo'lgani uchun o'zini qaytaramiz
input = "())" // 3 xil to'g'ri javob bor, istalganini qaytarish mumkin
output1 = "()" // oxirgi qavsni ochiramiz
output2 = "(())" // boshiga ochuvchi qavs qo'yamiz
output3 = "()()" // oxirgi qavsni teskari o'girib, oxiriga yopuvchi qavs qo'yamiz
Men flip - teskari o'girish amalini unutib qo'ydim va hayollarim boshqa taraflarga ketib vaqt yo'qotdim. 😖
Yechimni bera oldim. Kodini yozdim. Lekin uni "dry-run" qilib tekshirishga ulgurmadim.
Hozircha siz o'zingiz harakat qilib ko'ringchi. Keyinroq yechimini yozaman.