Leetcode 6. Zigzag Conversion

«PAYPALISHIRING» matni berilgan qatorlar soni bo’yicha zigzag ko’rinishida yozilgan. Uni qatorma-qator o’qib olish va qatorlar soni 3 bo’lganda «PAHNAPLSIIGYIR» ko’rinishida chiqarish kerak.

P   A   H   N
A P L S I I G
Y   I   R

Yoziladigan funksiya quyidagicha:

string convert(string s, int numRows);

Ishlash tartibi

Albatta intuitiv usul – bu matnni ikki o’lchamli massivga zigzag ko’rinishida to’ldirib chiqish bo’ladi. Lekin bunday holatda ishlash vaqti O(n² + n) ko’rinishiga keladi, sababi massivni to’ldirish O(n²) keyin undan string yasash kerak.

Yana bir – O(n) bilan bitadigan usuli ham bor. Biz uni ko’rib chiqamiz.

1. Matn uzunligiga qadar ishlaydigan for siklini ochamiz.
2. sikl qadami bo’yicha qator qadamini topamiz. U 0 va numRows orasida bo’lishi mumkin.
3. Qatorlarni matn harflari bilan to’ldirib boramiz.

for (let i = 0; i < str.length; i++) {
  // Pozitsiya 0 va numRows oralig'idagi son. 
  // U 0, 1, 2, ..., numRows, 0, 1, 2, ..., numRows ko'rinishida o'zgarib boradi.
  const pos = i % (2 * numRows - 2);

  // Qator raqamini topish
  const j = pos < numRows ? pos : 2 * numRows - 2 - pos;

  // Harflarni qator bo'yicha yig'ib boramiz.
  strNew[j] = strNew[j] ? strNew[j] + str[i] : str[i];
}

Natijada bizda bir o’lchamli strNew massivi hosil bo’ladi. Uni stringga o’tkazib, qaytaramiz.