Zigzag Conversion in Rust: An Optimized Approach

Introduction

The Zigzag Conversion problem is a classic string manipulation challenge that requires rearranging characters into a zigzag pattern across multiple rows and then reading them row by row. This article explores an optimized Rust solution, explaining each step and its computational efficiency.

Problem Statement

Given a string s and an integer num_rows, arrange s in a zigzag pattern across num_rows and return the result as a single concatenated string.

Example 1

Input:

s = "PAYPALISHIRING"
num_rows = 3

Zigzag Pattern:

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

Output:

"PAHNAPLSIIGYIR"

Example 2

Input:

s = "PAYPALISHIRING"
num_rows = 4

Zigzag Pattern:

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

Output:

"PINALSIGYAHRPI"

Understanding the Zigzag Pattern

1. Characters are placed diagonally and vertically.
2. Rows are filled in a “down-up” cycle:

• Move downward until reaching the last row.
• Move upward until reaching the first row.
• Repeat the cycle.

Pattern Formation

For num_rows = 3, s = "PAYPALISHIRING" is rearranged as:

Row 0: P   A   H   N
Row 1: A P L S I I G
Row 2: Y   I   R

Final output: "PAHNAPLSIIGYIR"

Optimized Approach

Key Observations

• Instead of modifying the original string, we store characters row-wise.
• We use a list of vectors (Vec<Vec<char>>) to store characters for each row.
• The zigzag movement is controlled using a step variable (1 for down, -1 for up).

Optimized Rust Solution

impl Solution {
    pub fn convert(s: String, num_rows: i32) -> String {
        let num_rows = num_rows as usize;
        if num_rows == 1 || s.len() <= num_rows {
            return s;
        }
        let mut rows = vec![Vec::new(); num_rows];
        let (mut i, mut step) = (0, 1);
        for c in s.chars() {
            rows[i].push(c);
            if i == 0 {
                step = 1;
            } else if i == num_rows - 1 {
                step = -1;
            }
            i = (i as isize + step) as usize;
        }
        rows.into_iter().flatten().collect()
    }
}

Code Explanation

Step 1: Handle Edge Cases

if num_rows == 1 || s.len() <= num_rows {
    return s;
}

• If num_rows == 1, there is no zigzag transformation; return s directly.
• If s.len() <= num_rows, each character fits into a row without forming a zigzag, so return s.

Step 2: Initialize Data Structures

let mut rows = vec![Vec::new(); num_rows];
let (mut i, mut step) = (0, 1);

• We create a Vec<Vec<char>> to store characters row-wise.
• i tracks the current row index.
• step is 1 (downward) initially.

Step 3: Traverse the String

for c in s.chars() {
    rows[i].push(c);

• Iterate over each character in s and append it to the correct row.

Step 4: Zigzag Direction Handling

if i == 0 {
    step = 1;
} else if i == num_rows - 1 {
    step = -1;
}
i = (i as isize + step) as usize;

• If at first row (i = 0) → Move down (step = 1).
• If at last row (i = num_rows — 1) → Move up (step = -1).
• Update i accordingly.

Step 5: Merge the Rows

rows.into_iter().flatten().collect()

• into_iter() → Converts Vec<Vec<char>> into an iterator.
• flatten() → Flattens all rows into a single sequence of characters.
• collect() → Converts the sequence into a String.

Time and Space Complexity Analysis

Time Complexity:

• O(n): Each character is processed once and inserted into a row.

Space Complexity:

• O(n): We store all characters in separate rows before concatenation.

Comparison with Naïve Approach

Final Thoughts

• The Zigzag Conversion problem can be solved efficiently using row-based traversal.
• The optimized Rust solution improves performance by:
• Eliminating unnecessary string concatenations.
• Using efficient data structures (Vec<Vec<char>>).
• Reducing time complexity to O(n).

This optimized approach ensures that even large inputs are handled efficiently, making it a robust solution.