Skip to content

Zigzag Conversion

class Solution {

    /**
     * @param String $s
     * @param Integer $numRows
     * @return String
     */
    function convert($s, $numRows) {
        $len = strlen($s);

        if ($numRows == 1 || $numRows >= $len) {
            return $s;
        }

        // Массив для хранения строк
        $finalString = '';
        $rows = array_fill(0, $numRows, "");

        $currentRow = 0;
        $goingDown = false;  // Направление (идем вниз или вверх по строкам)

        // Пройдем по каждому символу строки
        for ($i = 0; $i < $len; $i++) {
            // Добавляем символ в текущую строку
            $rows[$currentRow] .= $s[$i];

            // Если находимся в первой или последней строке, меняем направление
            if ($currentRow == 0 || $currentRow == $numRows - 1) {
                $goingDown = !$goingDown;
            }

            // Изменяем строку в зависимости от направления
            $currentRow += $goingDown ? 1 : -1;
        }

        // Собираем все строки в один результат
        foreach ($rows as $row) {
            $finalString .= $row;
        }

        return $finalString;
    }
}

Давайте подробно разберем, как работает алгоритм, особенно на примерах, с акцентом на вычисления и переходы по строкам в зигзагообразном паттерне.

Основной принцип

  1. Мы записываем строку в несколько строк, двигаясь сначала сверху вниз, затем снизу вверх.
  2. Для каждого символа строки мы добавляем его в одну из строк, определяемую текущей позицией.
  3. Когда мы достигаем верхней или нижней строки, меняем направление.

Пример 1: "PAYPALISHIRING" с numRows = 3

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

Как это работает:

  1. Строка: "PAYPALISHIRING", numRows = 3.
  2. Массив для строк: Массив из 3 строк, которые мы будем заполнять символами. Изначально все строки пусты:
rows = ["", "", ""]
  1. Мы начинаем с первого символа, который добавляется в первую строку (индекс 0):
rows[0] = "P"
  1. Переходим ко второму символу, который добавляется во вторую строку (индекс 1):
rows[1] = "A"
  1. Переходим к третьему символу, который добавляется в третью строку (индекс 2):
rows[2] = "Y"
  1. Теперь нам нужно вернуться в строку 1, и далее мы снова идем вниз. Следующий символ "P" добавляется в строку 1:
rows[1] = "AP"
  1. После этого добавляем символ в строку 0:
rows[0] = "PA"
  1. Потом добавляем символ в строку 1, и так далее. Весь процесс продолжается по тому же принципу — сначала вниз, потом вверх, и так по циклу.

Визуально:

Заполнение строк происходит так:

Позиция:   0    1    2    3    4    5    6    7    8    9    10   11   12  
Символы:  P    A    Y    P    A    L    I    S    H    I    R    I    N  
rows[0]:   P          A          H          N  
rows[1]:        A    P    L    S    I    I    G  
rows[2]:          Y          I          R

После того как все символы будут записаны в строки, мы просто их собираем:

rows[0] = "PAHN"
rows[1] = "APLSIIG"
rows[2] = "YIR"

Результат: "PAHNAPLSIIGYIR"

Пример 2: "mother" с numRows = 2

m   o   t   h   e   r

Пошаговое объяснение:

  1. Строка: "mother", numRows = 2.
  2. Массив для строк:
rows = ["", ""]

  1. Заполняем строки, двигаясь сверху вниз и потом вверх:

  2. Первый символ "m" идет в строку 0.

rows[0] = "m"
  • Второй символ "o" идет в строку 1.
rows[1] = "o"
  • Третий символ "t" идет обратно в строку 0.
rows[0] = "mt"
  • Четвертый символ "h" идет в строку 1.
rows[1] = "oh"
  • Пятый символ "e" идет снова в строку 0.
rows[0] = "mte"
  • Шестой символ "r" идет в строку 1.
rows[1] = "ohr"

Теперь мы собираем строки:

rows[0] = "mte"
rows[1] = "ohr"

Результат: "mohrte"

Пример 3: "A" с numRows = 1

Для строки из одного символа мы не делаем никаких изменений, просто возвращаем исходную строку.

Результат: "A"

Пояснение по шагам

  1. Мы начинаем с первого символа строки и добавляем его в строку с индексом currentRow.
  2. После каждого символа проверяем:
  3. Если мы находимся в верхней или нижней строке (currentRow == 0 || currentRow == numRows - 1), меняем направление.
  4. Направление меняется с "вниз" на "вверх", и наоборот.
  5. Когда все символы будут обработаны, строки из массива собираются в один результат.

Заключение

Этот алгоритм работает эффективно, даже если вы не хотите использовать стандартные зигзагообразные способы с массивами или другими сложными структурами данных. Алгоритм опирается на простое управление направлением и текущей строкой для создания желаемого зигзагообразного паттерна.