Leetcode 6 - Zigzag Conversion | oleh Aditya Dedhia

2 minggu, 1 hari yang lalu - macroblocks · 0 menit baca

LeetCode 6 - ZigZag Conversion

Topics: 💻 cs🏷️ problem📚 leetcode📄 medium

LeetCode Link: zigzag conversion writeup

Intuition

The key insight is recognising that we only need to track which row each character belongs to in the final zigzag pattern. So the most important decision is in the data structure; rather than building the entire 2D structure, we just need to determine which row a particular character belongs to, and we can achieve this using a counter that alternates direction at the boundaries.

Approach

The zigzag pattern alternates between going down (rows 0 to numRows-1) and going diagonally up (rows numRows-2 to 1). Instead of building the actual zigzag structure, we can simulate the movement by tracking which row each character belongs to, then concatenate all rows at the end.

1. Create a list of empty lists, one for each row

2. Use a counter i to track the current row and a boolean going_down to track direction

3. For each character:

Append it to the current row
Move to the next row (increment if going down, decrement if going up)
Change direction when hitting boundaries (i equals numRows or -1)

4. Concatenate all rows to build the final string

Complexity

Time complexity: O(n) (single pass through string)

Space complexity: O(n) (all characters distributed across numRows lists)

Solution

class Solution:

def convert(self, s: str, numRows: int) → str:

if numRows < 2: # no zigzag if not at least 2 rows
return s

row_values: list[list[str]] = [[] for i in range(numRows)]
going_down: bool = True
i: int = 0 # counter to track the row (dict key) adding char to

for char in s:
row_values[i].append(char)
if going_down:
i += 1
else:
i -= 1

if i == numRows:
going_down = False
i = numRows - 2 # skip bottom corner v case

if i == -1:
going_down = True
i = 1 # skip top corner v case

final_string: list = []
for row in row_values:
final_string.extend(row)
return ''.join(final_string)

blok

diskusi thread