Solution For Zigzag Conversion
ZigZag Conversion is a popular string manipulation problem on LeetCode. In this problem, you are given a string and the number of rows to be displayed. You are required to write a program that arranges the characters of the string in a zigzag pattern and returns the new string formed by the arrangement.
For example, if the string is “PAYPALISHIRING” and the number of rows is 3, the zigzag pattern would look like this:
P A H N
A P L S I I G
Y I R
The converted string would be “PAHNAPLSIIGYIR”.
To solve this problem, we can use an array of strings to store the characters in the zigzag pattern. Initially, we set all the elements in the array to empty strings. Then, we traverse the input string character by character and determine the row and column in the zigzag pattern where the character should be placed.
To determine the row and column, we use two variables – row and step. The variable row tracks the current row, and the variable step tracks the direction we are moving in. Initially, we set row to 0 and step to 1. We move right and up in the zigzag pattern until we reach the top row. When we reach the top row, we change the direction and start moving down and right until we reach the bottom row. We repeat this process until we have placed all the characters in the zigzag pattern.
Here is the Python code to solve the Zigzag Conversion problem:
“`
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows == 1:
return s
rows = [''] * numRows
row = 0
step = 1
for char in s:
rows[row] += char
if row == 0:
step = 1
elif row == numRows - 1:
step = -1
row += step
return ''.join(rows)
“`
In the above code, we first check if the number of rows is 1. If it is, we return the input string as it is, since there will be no zigzag pattern to be formed.
Next, we create an array of empty strings, one for each row in the zigzag pattern. We also initialize the variables row and step as 0 and 1, respectively.
We then iterate through each character in the input string and append it to the current row in the zigzag pattern using the += operator. We also change the direction of movement when we reach the top or bottom row.
Finally, we join all the rows in the array into a single string and return it.
This solution has a time complexity of O(n), where n is the length of the input string, since we traverse the string only once to form the zigzag pattern. The space complexity is O(numRows), since we use an array of n empty strings, one for each row in the pattern.
Step by Step Implementation For Zigzag Conversion
public class Solution {
public String convert(String s, int numRows) {
if (numRows == 1) return s;
StringBuilder ret = new StringBuilder();
int n = s.length();
int cycleLen = 2 * numRows - 2;
for (int i = 0; i < numRows; i++) {
for (int j = 0; j + i < n; j += cycleLen) {
ret.append(s.charAt(j + i));
if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
ret.append(s.charAt(j + cycleLen - i));
}
}
return ret.toString();
}
}class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows == 1:
return s
# Initialize empty list of strings for each row
rows = [''] * numRows
# Initialize row and direction
row, direction = 0, 1
# Iterate through characters in string
for c in s:
# Append character to appropriate row
rows[row] += c
# Change row and direction based on zigzag pattern
row += direction
if row == numRows - 1:
direction = -1
elif row == 0:
direction = 1
# Join all rows into a single string and return
return ''.join(rows)var convert = function(s, numRows) {
// create empty string to store converted string
// create an array of empty strings to store each row
// create a variable to keep track of the current row we are on
// create a variable to keep track of the current index in the string we are on
// create a variable to keep track of the direction we are going
let converted = "";
let rows = [];
for (let i = 0; i < numRows; i++) {
rows.push("");
}
let currRow = 0;
let currIndex = 0;
let goingDown = true;
// while we haven't reached the end of the string
// if we are going down
// add the current character to the row we are on
// increment the row
// else
// add the current character to the row we are on
// decrement the row
// if the current row is the first or last row
// reverse the direction we are going
// increment the current index
while (currIndex < s.length) {
if (goingDown) {
rows[currRow] += s[currIndex];
currRow++;
} else {
rows[currRow] += s[currIndex];
currRow--;
}
if (currRow === 0 || currRow === numRows - 1) {
goingDown = !goingDown;
}
currIndex++;
}
// concatenate all of the rows into one string and return it
for (let i = 0; i < rows.length; i++) {
converted += rows[i];
}
return converted;
};The code for the zigzag-conversion problem is as follows:
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1) return s;
string res = "";
int n = s.size();
int cycleLen = 2 * numRows - 2;
for (int i = 0; i < numRows; i++) {
for (int j = 0; j + i < n; j += cycleLen) {
res += s[j + i];
if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
res += s[j + cycleLen - i];
}
}
return res;
}
};/*
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
*/
public class Solution {
public string Convert(string s, int numRows) {
if (numRows == 1) return s;
StringBuilder ret = new StringBuilder();
int n = s.Length;
int cycleLen = 2 * numRows - 2;
for (int i = 0; i < numRows; i++) {
for (int j = 0; j + i < n; j += cycleLen) {
ret.Append(s[j + i]);
if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
ret.Append(s[j + cycleLen - i]);
}
}
return ret.ToString();
}
}