6. ZigZag Conversion

1
2
3
4
5
6
7
8
9
> FUNCTION main(): O(len(s)*numRows)
- DO      read user input and return problem output
- INPUT   string s(str)
          number of rows numRows(int)
- OUTPUT  answer (str)

idx_row_list <- list for indices of row per character
rows <- dictionary of row list containing characters corresponding index of row
concatenate characters

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from collections import defaultdict

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s

        def get_idx_row(idx_str):
            idx = idx_str % (2*numRows-2)
            if idx == 0:
                return 1
            elif idx == (2*numRows-2) // 2:
                return numRows
            else:
                return min(idx, (2*numRows-2)-idx)+1

        idx_row_list = [get_idx_row(idx_str) for idx_str in range(len(s))]

        rows = defaultdict(list)
        for idx_str, idx_row in enumerate(idx_row_list):
            rows[idx_row].append(s[idx_str])

        rst = ""
        for row in sorted(rows):
            rst += "".join(rows[row])
        return rst