LeetCode 6. Zigzag Conversion

October 30, 2024

This one took me about 15 minutes to come up with a solution. I then worked through it with this naive solution.

Solution

1class Solution:
2    def convert(self, s: str, numRows: int) -> str:
3        grid = [['' for column in range(len(s))] for row in range(numRows)]
4        x, y = 0, 0
5        direction = 1
6        for char in s:
7            grid[y][x] = char
8            if y == numRows - 1:
9                direction = -1
10                x += 1
11            elif direction == -1 and y > 0:
12                x += 1
13            elif direction == -1 and y == 0:
14                direction = 1
15            y += direction if numRows > 1 else 0
16        result = ""
17        for row in grid:
18            for char in row:
19                if char:
20                    result += char
21        return result

O(n) = n*m or n^2

Reflection

Looking back, I realized I didn't need to include the empty spaces as if it were illustrated. This allows me to simplify my code by using the append() method for lists. Here is my improved version:

1class Solution:
2    def convert(self, s: str, numRows: int) -> str:
3        if numRows == 1 or numRows >= len(s):
4            return s
5
6        grid = [[] for _ in range(numRows)]
7        y = 0 
8        direction = 1
9        for char in s:
10            grid[y].append(char)
11            if y == numRows - 1:
12                direction = -1
13            elif y == 0:
14                direction = 1
15            y += direction
16        
17        for i in range(len(grid)):
18            grid[i] = ''.join(grid[i])
19        result = ''.join(grid)
20        return result

LeetCode 12. Integer to Roman

LeetCode 28. Find the Index of the First Occurrence in a String