6. Zigzag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

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 = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:

Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

Example 3:

Input: s = "A", numRows = 1
Output: "A"

Constraints:

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

Problem Description

The task is to rearrange the characters of a given string s in a zigzag pattern on a specified number of rows and then read off the characters line by line to create a new string. The zigzag pattern means that the characters of s are placed diagonally in a zigzag manner in downwards and upwards directions successively. After placing all the characters in this pattern, we would read the characters in each row horizontally and concatenate to form the final string.

To visualize the process, you can think of writing down the characters in the following way:

  • Starting from the top row, write characters downwards.
  • Upon reaching the last row, switch direction and start writing characters upwards, forming a diagonal line until you reach the top row again.
  • Alternate the process until every character is written in this zigzag fashion.

For example, given a string "PAYPALISHIRING" and 3 rows, the characters should be placed like this:

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

After arranging the characters, the string "PAHNAPLSIIGYIR" is obtained by reading each row sequentially. To form this new string programmatically, the code should simulate the reading process.

Intuition

The intuitive approach to simulate the zigzag conversion process involves creating an imaginary 2D grid that represents rows and columns of the pattern. A group is defined which denotes the cycle length of the zigzag pattern, calculated as 2 * numRows - 2. If numRows is 1, then the zigzag pattern is not possible, and the original string is returned.

The solution uses a loop to construct the new string by considering each row individually, assembling the characters that would appear in that row in the zigzag pattern. The interval between characters of the same row varies depending on their position (at the top or bottom, it’s equal to one cycle; in between, it alternates between moving vertically down and obliquely up) and is used to calculate the index of the next character to be added.

  1. Initialize an empty list ans to hold characters in the order they should be added to form the zigzag string.
  2. Loop through each row. For the top and bottom rows, characters occur after every full cycle (the group), so the interval is constant. For intermediate rows, the interval alternates. We calculate the initial interval based on the current row.
  3. Within each row, loop to add characters to ans, incrementing the index by the interval each time. After each addition, update the interval to alternate between moving vertically and diagonally, accounting for edge cases to avoid a zero interval.
  4. After processing all rows, join the list of characters ans into a string to get the final result.

The core of the solution relies on finding the pattern of intervals between the positions within the zigzag alignment and using it to construct the final string efficiently without simulating the entire grid.

Solution Approach

The implementation for the given problem follows a direct approach that calculates the next index in the original string for each character in the transformed zigzag string. It does this by determining the appropriate index intervals without needing to simulate the entire 2D zigzag structure.

Here’s how the implementation works:

  1. Early Return for Single Row: If numRows is 1, the zigzag pattern is trivial and the original string can be returned immediately, as there is no alteration in the order of characters.if numRows == 1: return s
  2. Calculating the Group Cycle: The group cycle (group) is calculated as the number of characters that form the complete vertical and diagonal cycle in the zigzag pattern, given by 2 * numRows - 2. This number is central to the implementation as it helps to understand the symmetry in the pattern, which repeats every group characters.group = 2 * numRows - 2
  3. Initializing the Answer List: An empty list ans is initialized to store the characters in their new order.
  4. Populating Each Row: The algorithm iterates over each row and identifies the characters that would appear in that row in a zigzag pattern:
    • Determine the initial interval for characters in the current row. For the first and last rows, it remains constant and equal to group. For intermediate rows, the interval alternates between two values.
    • Use a while loop to continue adding characters to the ans list until the end of the string is reached.
    for i in range(1, numRows + 1): interval = group if i == numRows else 2 * numRows - 2 * i idx = i - 1 while idx < len(s): ans.append(s[idx]) idx += interval interval = group - interval if interval != group else intervalHere, i is the row index, idx is the index in the original string for the current character, and the interval determines the number of steps to the next character in the current row.
    • For intermediate rows (rows between the first and last), after each character is added, the interval for the next character is updated to the complementary interval (the difference between the group and the current interval), thus simulating the zigzag pattern without explicitly constructing a 2D grid structure.
  5. Concatenating the Results: After the rows are processed and all characters are placed in the ans list, the list is joined into a string to form the final zigzag transformed string.return ''.join(ans)

This implementation optimizes space by avoiding the creation of a 2D grid and computes the string in O(n) time by analyzing the inherent pattern in the positions of characters in the zigzag arrangement.

Example Walkthrough

Let’s consider a small example to illustrate the solution approach. Suppose we have the string "HELLO" and the number of rows numRows is 3. The task is to arrange the characters in a zigzag pattern and then read them line by line.

Step 1: Early Return for Single Row

Since numRows is not 1, we don’t return the string as is, and we proceed with the rest of the algorithm.

Step 2: Calculating the Group Cycle

We calculate the group cycle (group = 2 * numRows - 2) which in this case is 2 * 3 - 2 = 4. This means that the vertical and diagonal pattern will repeat every 4 characters.

Step 3: Initializing the Answer List

We initialize an empty ans list where we will store the characters.

Step 4: Populating Each Row

We iterate over each row and add the relevant characters to the ans list:

  • For the first row (i = 1), the interval will remain constant at 4. The first character is 'H' at index 0. The next character in the zigzag pattern for the first row would be 4 characters away, but since our string is shorter, we stop here for this row. So we add 'H'.
  • For the second row (i = 2), the interval starts at 2 * 3 - 2 * 2 = 2 and will alternate between 2 and (4 – 2) = 2 for subsequent characters. The first character for this row is 'E' at index 1. The next character in the zigzag pattern for the second row is 2 characters away, which is 'L' at index 3. There are no more characters 2 or 4 steps away, so we stop for this row. We add 'E' and 'L'.
  • For the third row (i = 3), the interval is constant at 4, the same as for the first row. The first character is 'L' at index 2, and there are no more characters 4 steps away. So, we add 'L'.

Step 5: Concatenating the Results

We concatenate the characters in the ans list to form the final string which is 'HEL'.

Following the steps above, the zigzag arrangement for the string "HELLO" with 3 rows would look like this:

H   .
. E .
L . .
. L .
. . O

When reading off each line, the new string formed is "HEL", which matches the characters collected in our answer list.

This walkthrough of a smaller example demonstrates how the designed algorithm would simulate the placement of characters in the zigzag pattern and construct the transformed string accordingly.

Solution Implementation

class Solution {
public:
    string convert(string s, int numRows) {
        // If there is only one row or the number of rows is greater than or equal to the length of the string, return the string as is
        if (numRows == 1 || numRows >= s.length()) {
            return s;
        }

        int idx = 0, d = 1;  // idx keeps track of the current row, d is the direction (1 for down, -1 for up)
        vector> rows(numRows);  // 2D vector to store characters for each row in the zigzag pattern

        // Traverse through each character in the input string
        for (char c : s) {
            rows[idx].push_back(c);  // Add the character to the current row
            // If we are at the top row, switch direction to down (1)
            if (idx == 0) {
                d = 1;
            // If we are at the bottom row, switch direction to up (-1)
            } else if (idx == numRows - 1) {
                d = -1;
            }
            // Update the row index based on the direction
            idx += d;
        }

        string result;  // String to hold the final result
        // Traverse each row and append its characters to the result string
        for (const auto& row : rows) {
            for (char c : row) {
                result += c;
            }
        }

        return result;  // Return the final result string
    }
};
Copied!
class Solution {
    public String convert(String s, int numRows) {
        // If there is only one row or the number of rows is greater than or equal to the length of the string, return the string as is
        if (numRows == 1 || numRows >= s.length()) {
            return s;
        }

        int idx = 0, d = 1;  // idx keeps track of the current row, d is the direction (1 for down, -1 for up)
        List[] rows = new ArrayList[numRows];  // Array to store lists representing each row in the zigzag pattern
        for (int i = 0; i < numRows; i++) {
            rows[i] = new ArrayList<>();  // Initialize each row as an empty ArrayList
        }

        // Traverse through each character in the input string
        for (char c : s.toCharArray()) {
            rows[idx].add(c);  // Add the character to the current row
            // If we are at the top row, switch direction to down (1)
            if (idx == 0) {
                d = 1;
            // If we are at the bottom row, switch direction to up (-1)
            } else if (idx == numRows - 1) {
                d = -1;
            }
            // Update the row index based on the direction
            idx += d;
        }

        StringBuilder result = new StringBuilder();  // StringBuilder to build the final result
        // Traverse each row and append its characters to the result string
        for (List row : rows) {
            for (char c : row) {
                result.append(c);
            }
        }

        return result.toString();  // Return the final result string
    }
}
Copied!
class Solution:
def convert(self, s: str, numRows: int) -> str:
    # If there is only one row or the number of rows is greater than or equal to the length of the string, return the string as is
    if numRows == 1 or numRows >= len(s):
        return s
    idx, d = 0, 1  # idx keeps track of the current row, d is the direction (1 for down, -1 for up)
    rows = [[] for _ in range(numRows)]  # List of lists to store characters for each row in the zigzag pattern
    # Traverse through each character in the input string
    for char in s:
        rows[idx].append(char)  # Add the character to the current row
        # If we are at the top row, switch direction to down (1)
        if idx == 0:
            d = 1
        # If we are at the bottom row, switch direction to up (-1)
        elif idx == numRows - 1:
            d = -1
        # Update the row index based on the direction
        idx += d
    # Join characters in each row to form a string
    for i in range(numRows):
        rows[i] = ''.join(rows[i])
    # Join all rows to form the final result string and return it
    return ''.join(rows)
Copied!
char* convert(char* s, int numRows) {
    // If there is only one row, the string remains unchanged, return it as is
    if (numRows == 1) return s;

    int len = strlen(s);  // Get the length of the input string
    char* a = (char*)malloc(len + 1);  // Allocate memory for the result string
    int index = 0;  // Index to track the position in the result string

    // Iterate through each row
    for (int i = 0; i < numRows; i++) {
        // Iterate through characters of the string that belong to this row
        for (int j = i; j < len; j += 2 * (numRows - 1)) {
            a[index++] = s[j];  // Add the character to the result string

            // If we are not at the top or bottom row, add the character from the "diagonal" position
            if (i > 0 && i < numRows - 1 && j + 2 * (numRows - 1) - 2 * i < len) {
                a[index++] = s[j + 2 * (numRows - 1) - 2 * i];  // Add the character diagonally
            }
        }
    }

    a[index] = '\0';  // Null-terminate the result string
    return a;  // Return the result string
}
Copied!
public class Solution {
    public string Convert(string s, int numRows) {
        // If there is only one row, return the string as is since no zigzag is possible
        if(numRows == 1)
            return s;
        
        // Initialize an array of StringBuilders, one for each row in the zigzag pattern
        StringBuilder[] sb = new StringBuilder[numRows];
        int currentRow = 0, direction = 1;  // currentRow tracks the current row, direction controls movement (1 for down, -1 for up)
        
        // Initialize each StringBuilder in the array to hold characters for that row
        for (int i = 0; i < sb.Length; i++) 
        { 
            sb[i] = new StringBuilder(); 
        }

        // Traverse each character in the input string
        for(int i = 0; i < s.Length; i++){
            sb[currentRow].Append(s[i]);  // Add the current character to the appropriate row (StringBuilder)
            
            // If we are at the last row, switch direction to move up
            if(currentRow == numRows - 1)
                direction = -1;
            // If we are at the first row, switch direction to move down
            else if(currentRow == 0)
                direction = 1;
            
            // Update the current row based on the direction
            currentRow = currentRow + direction;
        }

        // Create a StringBuilder to hold the final result
        StringBuilder result = new StringBuilder();
        
        // Append all rows' content from the StringBuilder array to the result
        for(int i = 0; i < numRows; i++)
            result.Append(sb[i]);

        // Return the final result as a string
        return result.ToString();
    }
}
Copied!
/**
* @param {string} s
* @param {number} numRows
* @return {string}
*/
var convert = function(s, numRows) {
    // If there is only one row or the number of rows is greater than or equal to the string length, return the string as is
    if(numRows === 1 || numRows >= s.length) return s;

    // Initialize an array to hold characters for each row in the zigzag pattern
    let rows = new Array(numRows).fill().map(() => []);
    let row = 0;  // Track the current row
    let down = false;  // Direction flag to control movement (downwards or upwards)

    // Loop through each character in the string
    for(const c of s) {
        rows[row].push(c);  // Add the current character to the corresponding row
        // Change direction at the first or last row
        if(row === 0 || row === numRows - 1) down = !down;
        // Move the row index down or up based on the direction flag
        row += down ? 1 : -1;
    }

    // Build the result string by joining all characters from each row
    let result = "";
    for(const r of rows) result += r.join("");  // Join the characters of each row and concatenate

    // Return the final result as a string
    return result;
};
Copied!
function convert(s: string, numRows: number): string {
    // If there's only one row, no zigzag conversion is needed, return the string as is
    if (numRows === 1) return s;

    // Initialize an array to hold the characters for each row in the zigzag pattern
    const rows = new Array(numRows).fill('');

    let currRow = -1;  // Start with an invalid row index
    let ascending = true;  // Direction flag: true for moving down, false for moving up

    // Loop through each character in the input string
    for (let i = 0; i < s.length; i++) {
        // Update the current row based on the direction
        currRow += ascending ? 1 : -1;
        rows[currRow] += s[i];  // Add the character to the current row

        // If we reach the last row, start moving upwards
        if (currRow === numRows - 1) {
            ascending = false;
        // If we reach the first row, start moving downwards
        } else if (currRow === 0) {
            ascending = true;
        }
    }

    // Join all rows together to form the final string and return it
    return rows.join('');
};
Copied!
class Solution {
    /**
     * @param String $s
     * @param Integer $numRows
     * @return String
     */
    function convert($s, $numRows)
    {
        // If numRows is 1 or greater than or equal to the length of the string, return the string itself
        if ($numRows <= 1 || $numRows >= strlen($s)) {
            return $s;
        }

        // Create an array to hold the strings for each row
        $rows = array_fill(0, $numRows, '');
        $curRow = 0;
        $goingDown = false;

        // Iterate through each character in the string
        for ($i = 0; $i < strlen($s); $i++) {
            $rows[$curRow] .= $s[$i]; // Append the character to the current row
            // Change direction if we hit the top or bottom row
            if ($curRow == 0) {
                $goingDown = true;
            } elseif ($curRow == $numRows - 1) {
                $goingDown = false;
            }
            // Move to the next row
            $curRow += $goingDown ? 1 : -1;
        }

        // Combine all rows into a single string
        return implode('', $rows);
    }
}
Copied!
class Solution {
    func convert(_ s: String, _ numRows: Int) -> String {
        // If the string is empty or there's only one row, return the string as is (no zigzag conversion needed)
        guard s != "" && numRows > 1 else { return s }
        
        // Initialize an array of strings to represent each row in the zigzag pattern
        var lines = Array(repeating: "", count: numRows)
        var idx = 0  // Current row index
        var flag = false  // Direction flag: true for moving up, false for moving down
        
        // Loop through each character in the string
        for ch in s {
            lines[idx].append(ch)  // Add the character to the appropriate row
            
            // Adjust the row index based on the current direction
            idx += flag ? -1 : 1
            
            // If we hit the top or bottom row, toggle the direction (up or down)
            if idx == -1 || idx == lines.count {
                idx += flag ? 2 : -2  // Adjust the index to stay within bounds
                flag.toggle()  // Toggle the direction (up/down)
            }
        }
        
        // Join all rows into a single string and return the result
        return lines.joined()
    }
}
Copied!
class Solution {
    fun convert(s: String, numRows: Int): String {
        // If there is only one row, return the string as is (no zigzag needed)
        if (numRows == 1) {
            return s
        }
    
        val result = StringBuilder()  // StringBuilder to hold the final result
        val n = s.length  // Length of the input string
        val interval = 2 * numRows - 2  // Interval that controls the movement between rows

        // Iterate over each row in the zigzag pattern
        for (i in 0 until numRows) {
            // For each row, iterate over the characters that belong to that row
            for (j in i until n step interval) {
                result.append(s[j])  // Append the character at position j to the result
                // If not in the top or bottom row, also add the character from the "diagonal" position
                if (i != 0 && i != numRows - 1 && j + interval - 2 * i < n) {
                    result.append(s[j + interval - 2 * i])
                }
            }
        }
    
        // Return the final result as a string
        return result.toString()
    }   
}
Copied!
class Solution {
  String convert(String s, int numRows) {
    String convert = "";  // Initialize the result string to hold the converted string

    // Create a list of strings (one for each row in the zigzag pattern)
    List<String> matrix = List.generate(numRows, (index) => "");
    int currentRow = 0;  // Track the current row
    bool isUp = true;  // Direction flag: true for moving down, false for moving up

    // If there is only one row, return the string as is (no zigzag pattern needed)
    if (numRows == 1) return s;

    // Loop through each character in the input string
    for (int i = 0; i < s.length; i++) {
      // If we move above the top row, reset to row 1 and change direction to down
      if (currentRow < 0) {
        currentRow = 1;
        isUp = true;
      }

      // If we reach the last row, change direction to move up
      if (currentRow >= numRows - 1) {
        currentRow = numRows - 1;
        isUp = false;
      }

      // Add the current character to the corresponding row in the matrix
      matrix[currentRow] += s[i];

      // Adjust the row based on the direction (down or up)
      if (isUp) {
        currentRow++;
      } else {
        currentRow--;
      }
    }

    // Concatenate all rows to form the final result string
    for (int i = 0; i < matrix.length; i++) {
      convert += matrix[i];
    }

    // Return the final zigzag-converted string
    return convert;
  }
}
Copied!

import "strings"
func convert(s string, numRows int) string {
    // If there's only one row, return the string as is (no zigzag conversion needed)
    if numRows == 1 {
        return s
    }

    // Initialize a strings.Builder to build the result efficiently
    var b strings.Builder
    b.Grow(len(s))  // Allocate enough space for the final string
    step := numRows * 2 - 2  // Calculate the full step size for zigzag pattern

    // Iterate over each row in the zigzag pattern
    for row := 0; row < numRows; row++ {
        nextStep := 0  // Variable to determine the step size for each row

        // For the first and last rows, the step size is equal to the full step size
        if row == 0 || row == numRows - 1 {
            nextStep = step
        } else {
            nextStep = row * 2  // For middle rows, the step size is row-specific
        }

        // Traverse the string by moving through positions for the current row
        for pos := row; pos < len(s); pos += nextStep {
            b.WriteByte(s[pos])  // Append the character to the result

            // For first and last rows, nextStep is the full step size
            if row == 0 || row == numRows - 1 {
                nextStep = step
            } else {    
                nextStep = step - nextStep  // Change step for the middle rows (zigzag effect)
            }
        }
    }

    // Return the final result as a string
    return b.String()
}
Copied!

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n). This is determined by the observation that we iterate over each character of the string s, which has length n. Every character is visited once during the construction of the ans list. The nested while loop does not increase the complexity because the inner loop’s increments are such that the total number of iterations remains linearly dependent on the length of the s.

Space Complexity

The space complexity of the code is O(n). This is because we use an additional list ans to store the rearranged characters. In the worst case, the ans list can contain all characters of the input string s, which requires space that is linearly proportional to the length of the input string.

Leave a Reply

Your email address will not be published. Required fields are marked *