6. Zigzag Conversion

Problem Description

The Zigzag Conversion problem involves converting a given string into a zigzag pattern with a specified number of rows. The pattern is read line by line, and the result should be the concatenation of each line.

For example, the string “PAYPALISHIRING” with 3 rows would result in “PAHNAPLSIIGYIR”.

---

---

Step by Step Algorithm

The solution to zigzag conversion can be achieved by using a simple loop to iterate through the characters of the input string and add them to the result string in the correct order.

1. Initialize a result string and a 2D array with the specified number of rows and the length of the input string.
2. Iterate through the characters of the input string.
3. Determine the row and column for each character based on the current iteration and the number of rows.
4. Add the character to the result string using the determined row and column.
5. Repeat steps 2-4 until all characters have been processed.
6. Return the result string

C#:

public class Solution {
    public string Convert(string s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        
        int n = s.Length;
        string[] rows = new string[numRows];
        int row = 0, direction = -1;
        
        for (int i = 0; i < n; i++) {
            rows[row] += s[i];
            
            if (row == 0 || row == numRows - 1) {
                direction *= -1;
            }
            
            row += direction;
        }
        
        return string.Join("", rows);
    }
}

C++:

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        
        int n = s.length();
        vector<string> rows(numRows);
        int row = 0, direction = -1;
        
        for (int i = 0; i < n; i++) {
            rows[row].push_back(s[i]);
            
            if (row == 0 || row == numRows - 1) {
                direction *= -1;
            }
            
            row += direction;
        }
        
        string result;
        for (int i = 0; i < numRows; i++) {
            result += rows[i];
        }
        
        return result;
    }
};

JavaScript:

var convert = function(s, numRows) {
    if (numRows === 1 || numRows >= s.length) {
        return s;
    }
    
    let rows = new Array(numRows).fill("");
    let index = 0;
    let step = 1;
    
    for (let i = 0; i < s.length; i++) {
        rows[index] += s[i];
        if (index === 0) {
            step = 1;
        } else if (index === numRows - 1) {
            step = -1;
        }
        index += step;
    }
    
    return rows.join("");
};

Python

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1 or numRows >= len(s):
            return s

        L = [''] * numRows
        index, step = 0, 1

        for x in s:
            L[index] += x
            if index == 0:
                step = 1
            elif index == numRows -1:
                step = -1
            index += step

        return ''.join(L)

Time and space complexity

Time Complexity: O(n), where n is the length of the input string. This solution iterates through the string once, taking constant time to append each character to the appropriate row.

Space Complexity: O(n), where n is the length of the input string. This solution creates a list of strings, with each string representing a row, taking O(n) space to store the final zigzag string.

Conclusion

In this blog post, we have seen a step-by-step algorithm to convert a string into a zigzag pattern. We have implemented the solution in four programming languages, namely C#, C++, JavaScript, and Python. The solution has a time complexity of O(n) and a space complexity of O(n), making it efficient for long strings. The algorithm is simple to understand and can be easily implemented in any programming language.