Teskari so'z
Berilgan stringni teskari tartibda qaytarish — string algoritmlaridagi eng asosiy masalalardan biri. Masalaning o'zi qisqa: belgilarni oxiridan boshiga qarab o'qish kerak.
Bu masala bir qarashda juda oddiy ko'rinadi, lekin uni hal qilishning ikki xil yo'li bor va ular xotiradan foydalanish jihatidan farqlanadi. Bundan tashqari, masala ba'zan so'zlar (words) darajasida ham beriladi: "har bir so'zni teskari qil" yoki "so'zlarning o'rnini almashtirib qo'y". Avval belgilar darajasidagi variantni ko'rib chiqamiz.
Birinchi g'oya: yangi joyga yozish
Eng intuitiv yondashuv — asl stringni oxiridan boshiga qarab o'qib, har bir belgini yangi joyga yozish:
FUNCTION teskari_yangi(s):
natija = bo'sh string
i = s.length - 1
WHILE i >= 0:
natija ga s[i] qo'sh
i = i - 1
RETURN natija
Bu yondashuv to'g'ri ishlaydi. Lekin u n uzunlikdagi natija uchun O(n) qo'shimcha xotira talab qiladi.
Agar natijani yangi joyga yozishning hech qanday cheklovi bo'lmasa, bu yondashuv to'liq yetarli. Lekin agar masala "joyida o'zgartirish" (in-place) yoki "qo'shimcha O(n) xotira ishlatmasdan" desa, ikkinchi yondashuv kerak bo'ladi.
Ikki ko'rsatkich: joyida almashtirish
Samaraliroq yondashuv — ikkita ko'rsatkich yordamida belgilarni joyida almashtirish. Biri boshidan, biri oxiridan boshlab, ular uchrashgunga qadar har qadamda mos belgilarni o'zaro almashtiradi:
FUNCTION teskari_joyida(s):
l = 0
r = s.length - 1
WHILE l < r:
s[l] va s[r] ni o'zaro almashtir
l = l + 1
r = r - 1
Bu yondashuv qo'shimcha xotira sarflamaydi. Faqat ikkita ko'rsatkich — l va r — saqlanadi.
Dry run: bosqichma-bosqich kuzatish
"salom" (5 belgi) ustida kuzatib chiqamiz:
Boshlang'ich holat:
indeks: 0 1 2 3 4
[s] [a] [l] [o] [m]
^ ^
l r
Qadam 1: s[0]='s' va s[4]='m' almashadi
[m] [a] [l] [o] [s]
^ ^
l r (l=1, r=3)
Qadam 2: s[1]='a' va s[3]='o' almashadi
[m] [o] [l] [a] [s]
^
l=2, r=2
l < r sharti bajarilmaydi (2 < 2 yolg'on).
Tsikl to'xtaydi.
Natija: "molas"
Ko'rsatkichlar uchrashganda (l == r, toq uzunlik) yoki o'tib ketganda (l > r, juft uzunlik) tsikl to'xtaydi. l < r sharti ikkala holatni ham to'g'ri boshqaradi.
Note
Agar l < r o'rniga l != r yozilsa, juft uzunlikdagi stringda ko'rsatkichlar bir-birini o'tib ketadi va tsikl cheksiz davom etishi mumkin. To'xtash sharti muhim.
Juft uzunlikdagi misol
"dastur" (6 belgi) ustida:
Boshlang'ich:
[d] [a] [s] [t] [u] [r]
^ ^
l=0 r=5
Qadam 1: 'd' ↔ 'r'
[r] [a] [s] [t] [u] [d]
^ ^
l=1 r=4
Qadam 2: 'a' ↔ 'u'
[r] [u] [s] [t] [a] [d]
^ ^
l=2 r=3
Qadam 3: 's' ↔ 't'
[r] [u] [t] [s] [a] [d]
^
l=3, r=2
l < r sharti bajarilmaydi (3 < 2 yolg'on).
Tsikl to'xtaydi.
Natija: "rutsad"
So'zlarni teskari qilish
Ba'zan masala butun stringni emas, uning ichidagi har bir so'zni teskari qilishni talab qiladi:
Bunday holda string avval bo'sh joy bo'yicha so'zlarga bo'linadi, keyin har bir so'z teskari qilinadi, so'ng qaytadan birlashtiriladi.
Boshqa bir variant — so'zlarning tartibi teskari qilinadi, belgilar esa o'z joyida qoladi:
Bu masala uchun klassik yondashuv: avval butun stringni teskari qil, keyin har bir so'zni alohida teskari qil. Natijada so'zlar tartib bo'yicha teskari, lekin ichidagi belgilar to'g'ri bo'ladi.
Chegara holatlari
Bo'sh string: l = 0, r = -1. l < r shart darhol yolg'on. Tsikl boshlanmaydi. Natija bo'sh string — to'g'ri.
Bitta belgi: l = 0, r = 0. 0 < 0 yolg'on. Belgi o'z joyida qoladi — to'g'ri.
Palindrom: Teskari qilib ko'rish va asl string bir xil bo'ladi. Algoritm to'g'ri ishlaydi, natija asl string bilan bir xil.
Bir xil belgilardan iborat string: "aaaa". Almashtirish bajariladi, lekin natija o'zgarmaydi. Algoritm to'g'ri ishlaydi.
Vaqt va xotira murakkabligi
| Yondashuv | Vaqt murakkabligi | Xotira murakkabligi |
|---|---|---|
| Yangi joyga yozish | O(n) | O(n) |
| Ikki ko'rsatkich (joyida) | O(n) | O(1) |
Ikkala yondashuv ham O(n) vaqtda ishlaydi. Asosiy farq xotirada: biri natija uchun O(n) joy talab qilsa, ikkinchisi faqat ikkita ko'rsatkich bilan O(1) da ishlaydi.
Aniqroq aytganda, ikki ko'rsatkich yondashuvida n/2 marta almashtirish bajariladi. Bu O(n/2), amortizatsiya qilinganda O(n).
Qachon qaysi yondashuv?
Agar masala qo'shimcha xotira ishlatishga ruxsat bersa va immutable string bilan ishlayotgan bo'lsangiz (ko'pgina tillarning string modeli immutable), yangi string qurish to'g'ri yo'l. Agar mutable belgilar massivi bilan ishlayotgan bo'lsangiz yoki O(1) xotira shart bo'lsa, ikki ko'rsatkich yondashuvi mos.
Bu masala to'g'ridan-to'g'ri qo'llanish doirasi keng — palindromni tekshirish, so'zlar tartibini o'zgartirish va boshqa ko'plab string masalalarida teskari aylantirish asosiy qurilish bloki bo'lib xizmat qiladi.