Пример решения задачи #6. Python LeetCode, Zigzag Conversion

Вариант решения задачи на Python с LeetCode

Категория: Алгоритмы.
Название задачи: Zigzag Conversion.
Сложность: Средняя.
Статус решения: "Решено".

Условие задачи:
Строка "PAYPALISHIRING" записывается в виде зигзагообразного узора на заданном количестве строк. Например, для 3 строк узор будет выглядеть так (рекомендуется использовать моноширинный шрифт для лучшей читаемости):

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

После этого строки считываются последовательно, и в результате получается строка: "PAHNAPLSIIGYIR".

Необходимо написать функцию, которая преобразует заданную строку в такой зигзагообразный формат и возвращает результат в виде новой строки. Функция должна принимать два параметра: исходную строку s и количество строк

Решение:

Python

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        # Если количество строк равно 1 или больше либо равно длине строки,
        # то строка не меняется, так как она уже в зигзаге.
        if numRows == 1 or numRows >= len(s):
            return s

        # Создаем список строк, где каждая строка будет представлять одну строку зигзага.
        zigzag = [''] * numRows

        # Переменная для отслеживания текущей строки.
        row = 0

        # Переменная для определения направления движения (вниз или вверх).
        step = 1

        # Проходим по каждому символу в строке.
        for char in s:
            # Добавляем текущий символ в соответствующую строку зигзага.
            zigzag[row] += char

            # Если мы достигли верхней границы (row == 0), двигаемся вниз.
            if row == 0:
                step = 1
            # Если мы достигли нижней границы (row == numRows - 1), двигаемся вверх.
            elif row == numRows - 1:
                step = -1

            # Обновляем текущую строку в зависимости от направления движения.
            row += step

        # Склеиваем все строки зигзага в одну результирующую строку.
        return ''.join(zigzag)

Объяснение кода

Проверка граничных условий:
Если numRows равно 1 или больше либо равно длине строки s, то строка не требует преобразования, так как она уже находится в зигзаге. В этом случае просто возвращаем исходную строку.

Создание списка для хранения строк зигзага:
Мы создаем список zigzag, содержащий numRows пустых строк. Каждая строка будет представлять одну строку зигзага.

Переменные для отслеживания текущей строки и направления движения:
row — это индекс текущей строки в списке zigzag.
step — это переменная, которая определяет направление движения: 1 означает движение вниз, а -1 — движение вверх.

Обход строки s:
Для каждого символа в строке s:
Добавляем его в соответствующую строку зигзага (zigzag[row]).
Если мы достигли верхней границы (row == 0), начинаем двигаться вниз (step = 1).
Если мы достигли нижней границы (row == numRows - 1), начинаем двигаться вверх (step = -1).
Обновляем значение row в зависимости от направления движения.

Формирование результата:
После обработки всех символов строки s, склеиваем все строки из списка zigzag в одну результирующую строку с помощью метода ''.join(zigzag).

Пример работы:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Источник решения: hdhai.com