The LeetCode Zigzag Conversion Problem in TypeScript

Strings and their manipulations are integral to web development. Whether we're handling user input, parsing JSON responses, or simply formatting text for display, understanding strings is crucial. The Zigzag Conversion problem is an interesting exploration of string manipulation, particularly in the context of array indexing and mathematics.

What is the Zigzag Conversion Problem?

The Zigzag Conversion problem is a classic coding interview challenge. Given a string and a number of rows, your task is to write the string in a zigzag pattern across the specified number of rows and then return the result as a single string read row by row.

For example, the string ZIGZAGCONVERSION when written in a zigzag pattern across three rows would look like this:

And in code, would look like this:

Z   A   N   SI Z G O V R I NG   C   E   O

When read row‑by‑row, the result is ZANSIZGOVRINGCEO.

To offer another example, this the string PAYPALISHIRING (which I've taken directly from the LeetCode problem page), also over three rows:

P   A   H   NA P L S I I GY   I   R

When reading this row‑by‑row, the result is PAHNAPLSIIGYIR.

It potentially sounds more complex than it actually is, but the complexity comes from increasing the number of rows; as the number of rows increases, so does the complexity of indexing each character correctly.

Approaches to a Solution

When it comes to actually coding a solution, there are four distinct approaches that come to mind (much like a similar problem I'm currently working on):

1. Iteration with Direction Control

   : Using a single pass through the string whilst controlling the direction of the placement of characters, either going "down" the rows or "up".

2. Visit Characters in the Original String:

   Calculate the exact interval between characters in the original string for each row of the zigzag pattern and visit them directly.

3. Use of Additional Data Structures:

   Like a 2D array, to simulate the entire zigzag pattern and then consolidate that back into a single string.

4. Direct Mathematical Calculation:

   Predict the position of each character in the final string directly, using the mathematical properties of the zigzag pattern.

1. Iteration with Direction Control

The idea here is to iterate over the string character by character and place each character into the appropriate row. We control the direction we move in (either up or down) based on our current position.

The Code

In JavaScript (TypeScript), this would be fairly simple and would look like this:

const convert = (s: string, numRows: number): string => {  if (numRows === 1) return s;  const rows: string[] = new Array(Math.min(numRows, s.length)).fill('');  let currentRow: number = 0;  let goingDown: boolean = false;  for (const char of s) {    rows[currentRow] += char;    if (currentRow === 0 || currentRow === numRows - 1) goingDown = !goingDown;    currentRow += goingDown ? 1 : -1;  }  return rows.join('');};

How It Works

We initialise an array of rows as strings. As we loop through the characters in the input string, we append each character to its respective row in the rows array. We then change our direction (going up or down) whenever we reach the top or bottom row.

To return the result, we simply join these arrays together as a string.

2. Visit Characters in the Original String

This method is more direct. Instead of placing characters into rows as we go, we can calculate the exact interval between characters in the original string, for each row of the zigzag pattern, and visit them directly.

The Code

const convertDirect = (s: string, numRows: number): string => {  if (numRows === 1) return s;  const len: number = s.length;  const cycleLen: number = 2 * numRows - 2;  let result: string = '';  for (let i = 0; i < numRows; i++) {    for (let j = 0; j + i < len; j += cycleLen) {      result += s[j + i];      if (i != 0 && i != numRows - 1 && j + cycleLen - i < len) {        result += s[j + cycleLen - i];      }    }  }  return result;};

How It Works

Instead of just working our way through the input pushing each character into a row array, here we first determine the "cycle" of characters in our zigzag pattern. Then, by iterating through our rows and cycles, we can pick out each character from our original string that belongs in the final result.

3. Use of Additional Data Structures

So far, we've just used strings of characters to represent each row in the pattern. However, we could also simulate the entire zigzag pattern using a 2D array or another suitable data structure. Once the entire pattern has been constructed, we can then consolidate it into a single string.

The Code

From this point onwards, the solutions ‑ and the code ‑ become a little more complex. Nevertheless, I believe I have a working solution using a 2D array:

const convertUsing2D = (s: string, numRows: number): string => {  if (numRows === 1 || s.length <= numRows) return s;  // Initialise 2D matrix  const matrix: string[][] = Array.from({ length: numRows }, () => []);  let row: number = 0;  let direction: 'down' | 'up' = 'down';  for (const char of s) {    matrix[row].push(char);    // Decide direction    if (row === 0) {      direction = 'down';    } else if (row === numRows - 1) {      direction = 'up';    }    row += direction === 'down' ? 1 : -1;  }  // Convert 2D matrix to string  let result: string = '';  for (const line of matrix) {    result += line.join('');  }  return result;};

How It Works

1. We first create an empty 2D matrix (a list of empty lists, one for each row).
2. As we iterate over the string, we place each character into the appropriate row based on our current direction (either going "down" or "up").
3. We change direction when we reach the top or bottom of the matrix.
4. After populating the matrix, we then convert it back into a string by iterating through each row and joining the characters together.

Compared to the previous two solutions, this approach is more resource‑intensive, but it provides a clear, visual representation of the zigzag pattern, which can be useful for debugging and understanding the problem.

4. Direct Mathematical Calculation

Finally, for those who are mathematically inclined, the zigzag pattern can be deciphered to predict the position of each character in the final string directly. Whilst this approach might not always be the most readable, it is an exciting exploration of the problem.

Here, we want to leverage the mathematical relationship between the characters' positions in the output string and their positions in the original string. For the Zigzag Conversion problem, the "zigzag" pattern can be seen as a cycle where the length of each cycle (from the top of one "zig" to the top of the next) can be calculated as 2*numRows ‑ 2.

Holding this in mind, we can use the following approach:

1. Handle the characters in the first and last rows separately since they don't form full zigzags. They only appear every cycleLen positions.
2. For all the other characters, two positions from the original string will be mapped into one cycle of the zigzag pattern.

Here's a JavaScript (TypeScript) implementation that demonstrates this method:

const convertDirectMath = (s: string, numRows: number): string => {  if (numRows === 1 || s.length <= numRows) return s;  const cycleLen: number = 2 * numRows - 2;  let result: string = '';  for (let i = 0; i < numRows; i++) {    for (let j = 0; j + i < s.length; j += cycleLen) {      // Characters from the original string that fall vertically in the pattern      result += s[j + i];      // Characters from the original string that fall diagonally in the pattern      // Ensure it's not the first and last row      if (i !== 0 && i !== numRows - 1 && j + cycleLen - i < s.length) {        result += s[j + cycleLen - i];      }    }  }  return result;};

How It Works

1. We first calculate the cycle length, which represents the length of each zigzag pattern.
2. For the characters in the first and last rows, they appear every cycleLen positions, so we can directly compute their positions.
3. For the middle rows, two characters from the original string are mapped to each cycle: one that falls vertically and another that falls diagonally.
4. The vertical one is at j + i and the diagonal one is at j + cycleLen ‑ i.

Of the solutions, this one could be considered more efficient since it computes the position of each character directly, without having to simulate the zigzag pattern. This leads to a faster ‑ albeit more complex ‑ solution.

Comparison and Conclusion

Iteration with Direction Control is conceptually straightforward and often the first solution that comes to mind. It is also relatively space‑efficient as it doesn't require the storage of a 2D grid.

Visit Characters in the Original String is a step up in optimisation, exploiting the periodic nature of the zigzag pattern. While it might be slightly harder to grasp initially, it can be faster, especially for long strings.

Use of Additional Data Structures offers an intuitive visualisation of the problem, making it easier to debug or explain. However, it is not the most space‑efficient.

Direct Mathematical Calculation is more of an academic exercise and might not be the most practical in real‑world applications due to its complexity.

Obviously, the likelihood of a web developer coming across this problem as a genuine, real‑world requirement (rather than something an interviewer might present to you) is very slim. However, the Zigzag Conversion problem, whilst a coding challenge at its heart, underlines the importance of string manipulation, a cornerstone in the domain of web applications.

By examining and mastering different methods of solving such problems, we hone our web development skills, readying ourselves for the diverse challenges the field throws at us.