ZigZag Conversion

تاریخ: جلسه ۲ - ۱۸ مرداد ۱۴۰۳

صورت سوال

فرمت زیگزاگِ ۳ ردیفی را برای رشته‌ای چون "PAYPALISHIRING" به صورت زیر تعریف می‌کنیم:

P   A   H   N

A P L S I I G

Y   I   R

و ردیف به ردیف به صورت "PAHNAPLSIIGYIR" خوانده می‌شود.

قطعه کدی بنویسید که این تبدیل را انجام دهد.

string convert(string s, int numRows);

مثال ۱:

ورودی: s = "PAYPALISHIRING", numRows = 3

خروجی: "PAHNAPLSIIGYIR"

مثال ۲:

ورودی: s = "PAYPALISHIRING", numRows = 4

خروجی: "PINALSIGYAHRPI"

توضیحات:

P     I    N

A   L S  I G

Y A   H R

P     I

مثال ۳:

ورودی: s = "A", numRows = 1

خروجی: "A"

قیدهای مسئله:

1 <= s.length <= 1000
رشته s شامل حروف انگلیسی، اعداد، علامت‌ها و space است.
1 <= numRows <= 1000

پاسخ سوال

def find_zigzag(word, row):

    divide_factor = 2 * row - 2

    zigzag_string = ""

    for r in range(row):

        indices = []

        pointer = r

        i = divide_factor - 2 * r

        j = 2 * r

        i_or_j = 0

        if row == 1:

            zigzag_string = word

            break

        while pointer < len(word):

            indices.append(pointer)

            difference = (1 - i_or_j) * i + i_or_j * j

            difference = difference if difference != 0 else divide_factor

            pointer += difference

            i_or_j = (i_or_j + 1) % 2



        for index in indices:

            zigzag_string += word[index]



    return zigzag_string




word = "PAYPALISHIRING"

row = 3

print(find_zigzag(word=word, row=row))

توضیح:

ایده پشت این راه‌حل این است:

P   A   H   N

A P L S I I G

Y   I   R



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

0 1 2 3 4 5 6 7 8 9 10 11 12 13

اندیس کاراکترهای خط اول عبارت است از:

row 1 = 0, 4, 8, 12

row 2 = 1, 3, 5, 7, 9, 11, 13

row 3 = 2, 6, 10

همانطور که مشخص است، برای ردیف اول اندیس ها ۴ تا ۴ تا جلو می‌رود.

برای ردیف دوم اندیس ها ۲ تا ۲ تا جلو می‌رود.

برای ردیف سوم اندیس ها ۴ تا ۴ تا جلو می‌رود.

یک مثال دیگر را هم بررسی می‌کنیم.

P     I    N

A   L S  I G

Y A   H R

P     I



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

0 1 2 3 4 5 6 7 8 9 10 11 12 13

اندیس ها:

row 1 = 0, 6, 12

row 2 = 1, 5, 7, 11, 13

row 3 = 2, 4, 8, 10

row 4 = 3, 9

ردیف اول ۶ تا ۶ تا.

ردیف دوم اول ۴ تا بعد ۲ تا. دوباره ۴ تا بعد ۲ تا و ...

ردیف سوم اول ۲ تا بعد ۴ تا. دوباره ۲ تا بعد ۴ تا و ...

ردیف چهارم هم ۶ تا ۶ تا.

دقت شود که مجموع ۴ و ۲ نیز ۶ میشود.

پس شاید الگویی وجود داشته باشد. اما این ۶ ای که ردیف اول با آن جلو می‌رود و ۴ ای که در ردیف اول مثال قبل دیدیم از کجا می‌آیند؟

وقتی ما کاراکتر اول را در ردیف اول می‌گذاریم، row - 1 ردیف به پایین و سپس row - 1 ردیف به بالا حرکت می‌کنیم تا دوباره به ردیف اول برسیم. یعنی مجموعا

2 * row - 2

ردیف. که در مثال اول با ۳ ردیف به عدد ۴ میرسیم و در مثال دوم با ۴ ردیف به عدد ۶.

حالا برای درک بهتر رفتار ردیف های بعدی اینطور فرض می‌کنیم که ردیف اول به جای اینکه ۶ تا ۶ تا به جلو برود، ۶ تا ۰ تا به جلو می‌رود! یعنی اول ۶ خانه به جلو می‌رود بعد هیچ خانه‌ای جلو نمی‌رود و دوباره ۶ خانه به جلو می‌رود. (که در واقع همان ۶ تا ۶ تاست)

حالا وقتی به رفتار ردیف‌های بعدی نگاه می‌کنیم، انگاری که از ۶ تا ۰ تا، به ۴ تا ۲ تا رسیده‌اند. یعنی ۲ تا از پرش اول کم شده و به پرش دوم اضافه شده. این الگو را به این صورت می‌نویسیم:

row 1 = 6, 0, 6, 0, ...

row 2 = 4, 2, 4, 2, ...

row 3 = 2, 4, 2, 4, ...

row 4 = 0, 6, 0, 6, ...

کد بالا در واقع پیاده‌سازی این ایده است.