Problem

You’re a shop sign designer, designing a dynamic digital sign for a trendy food truck called Burrito Truck. To catch the attention of hungry passersby, you want to display the restaurant’s name in a visually striking zigzag pattern.

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

And then read line by line: "PAHNAPLSIIGYIR "

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

Example 1:

Input: s = “HELLOWORLD”, numRows = 3
Output: “HOLELWRLOD”
Explanation:
H O L
E L W R L
L D

Example 2:

Input: s = “OPENAIROCKS”, numRows = 4
Output: “ORCAEIPNSOK”
Explanation:
O R C
P E I N S
E A O K
N S

Example 3:

Input: s = “PROGRAMMING”, numRows = 5
Output: “PGIRMORMANG”
Explanation:
P G
R I M
O R A
G M N
M

Example 4:

Input: s = “DATASTRUCTURE”, numRows = 2
Output: “DTSRCRUTAAUCET”
Explanation:
D T S R C R U T R
A A U C E

Example 5:

Input: s = “CHATGPT”, numRows = 1
Output: “CHATGPT”
Explanation:
C H A T G P T

Constraints:

1 <= s.length <= 1000
s consists of English letters (lower-case and upper-case), ',' and '.'.
1 <= numRows <= 1000

Java Solution

class Solution {
  public String convert(String s, int numRows) {
    StringBuilder sb = new StringBuilder();
    List<Character>[] rows = new List[numRows];
    int k = 0;
    int direction = numRows == 1 ? 0 : -1;

    for (int i = 0; i < numRows; ++i)
      rows[i] = new ArrayList<>();

    for (final char c : s.toCharArray()) {
      rows[k].add(c);
      if (k == 0 || k == numRows - 1)
        direction *= -1;
      k += direction;
    }

    for (List<Character> row : rows)
      for (final char c : row)
        sb.append(c);

    return sb.toString();
  }
}

If the number of rows is 1 or is greater than or equal to the length of the string, the string is just returned as is.
Create an array called “rows” to contain the characters that would reside in each row of the zigzag pattern.
Iterate through the string one character at a time.
For each character in the string, place it into the appropriate row of the “rows” array.
Determine whether the next character should be placed in the row above or below the current row by checking if the current row is 0 (at the top) or equal to the number of rows minus 1 (at the bottom). If at the top or the bottom, the direction will change.
Update the current row index according to the direction (going up or down).
After iterating through the entire string, join the rows array into a single string and return it.

C++ Solution

class Solution {
 public:
  string convert(string s, int numRows) {
    string ans;
    vector<vector<char>> rows(numRows);
    int k = 0;
    int direction = (numRows == 1) - 1;

    for (const char c : s) {
      rows[k].push_back(c);
      if (k == 0 || k == numRows - 1)
        direction *= -1;
      k += direction;
    }

    for (const vector<char>& row : rows)
      for (const char c : row)
        ans += c;

    return ans;
  }
};

If the number of rows is 1 or is greater than or equal to the length of the string, the string is just returned as is.
Create an array called “rows” to contain the characters that would reside in each row of the zigzag pattern.
Iterate through the string one character at a time.
For each character in the string, place it into the appropriate row of the “rows” array.
Determine whether the next character should be placed in the row above or below the current row by checking if the current row is 0 (at the top) or equal to the number of rows minus 1 (at the bottom). If at the top or the bottom, the direction will change.
Update the current row index according to the direction (going up or down).
After iterating through the entire string, join the rows array into a single string and return it.

Python Solution

class Solution:
  def convert(self, s: str, numRows: int) -> str:
    rows = [''] * numRows
    k = 0
    direction = (numRows == 1) - 1

    for c in s:
      rows[k] += c
      if k == 0 or k == numRows - 1:
        direction *= -1
      k += direction

    return ''.join(rows)

1. If the number of rows is 1 or is greater than or equal to the length of the string, the string is just returned as is.

Create an array called “rows” to contain the characters that would reside in each row of the zigzag pattern.
Iterate through the string one character at a time.
For each character in the string, place it into the appropriate row of the “rows” array.
Determine whether the next character should be placed in the row above or below the current row by checking if the current row is 0 (at the top) or equal to the number of rows minus 1 (at the bottom). If at the top or the bottom, the direction will change.
Update the current row index according to the direction (going up or down).
After iterating through the entire string, join the rows array into a single string and return it.

JavaScript Solution

function convert(s, numRows) {
    if (numRows === 1 || numRows >= s.length) return s;

    let rows = new Array(numRows).fill("");
    let curRow = 0;
    let goingDown = false;

    for (let c of s) {
        rows[curRow] += c;
        if (curRow === 0 || curRow === numRows - 1) goingDown = !goingDown;
        curRow += goingDown ? 1 : -1;
    }

    return rows.join("");
}

1. If the number of rows is 1 or is greater than or equal to the length of the string, the string is just returned as is.

Create an array called “rows” to contain the characters that would reside in each row of the zigzag pattern.
Iterate through the string one character at a time.
For each character in the string, place it into the appropriate row of the “rows” array.
Determine whether the next character should be placed in the row above or below the current row by checking if the current row is 0 (at the top) or equal to the number of rows minus 1 (at the bottom). If at the top or the bottom, the direction will change.
Update the current row index according to the direction (going up or down).
After iterating through the entire string, join the rows array into a single string and return it.

Rewording1: In this real-world example, imagine you are tasked with organizing a list of employee names in a zigzag pattern across multiple rows. This might be useful if you want to display the names in an aesthetically pleasing way on a website or a document, but need to keep them organized and easy to read.

The problem can be visualized as follows: Given a string (in this case, a list of employee names) and a specific number of rows, how would one arrange the characters in a zigzag pattern?

To understand this better, let’s break down the process. First, we have an initial string - “PAYPALISHIRING”. If we want to display this string in a zigzag pattern with 3 rows, it can be arranged as follows:

For characters in the first row and third row (odd rows), they are placed at positions where their column number is equal to position modulus 2.
For characters in the second row (even rows), they are placed alternately between the odd rows.

This results in the following pattern:

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

Reading this zigzag pattern line by line gives us the final result: “PAHNAPLSIIGYIR”.

The same process can be applied to different strings and numbers of rows, as demonstrated in the examples provided.

This problem relates to algorithms for string manipulation and array formation. The solution typically involves two nested loops - one for iterating through the input string and another for handling each row. Depending on whether a row is an odd or even numbered row, you will place characters at specific indices. Once all characters are placed in their respective rows, they can be combined to form the final zigzag pattern.

In summary, this real-world example involves arranging a list of items (in this case, employee names) in a zigzag pattern across multiple rows for organizational and aesthetic purposes.

Problem#

Java Solution#

C++ Solution#

Python Solution#

JavaScript Solution#

Problem

Java Solution

C++ Solution

Python Solution

JavaScript Solution