Description:
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);
Examples:
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"Solution in Python:
To solve the problem of converting a string into a zigzag pattern on a given number of rows, and then reading it line by line, we can follow these steps:
- Create a list of strings for each row.
- Iterate through the characters in the string and place them in the appropriate row.
- Concatenate the strings from all rows to get the final result.
Python
class Solution:
def convert(self, s: str, numRows: int) -> str:
# If numRows is 1, return the string as is since there's no zigzag pattern
if numRows == 1:
return s
# Initialize a list of strings for each row
rows = [''] * min(numRows, len(s))
cur_row = 0
going_down = False
# Iterate over each character in the input string
for char in s:
rows[cur_row] += char
# Change direction when you reach the top or bottom row
if cur_row == 0 or cur_row == numRows - 1:
going_down = not going_down
# Move up or down in the rows
cur_row += 1 if going_down else -1
# Join all rows to get the final result
return ''.join(rows)
# Example usage:
sol = Solution()
print(sol.convert("PAYPALISHIRING", 3)) # Output: "PAHNAPLSIIGYIR"
print(sol.convert("PAYPALISHIRING", 4)) # Output: "PINALSIGYAHRPI"
print(sol.convert("A", 1)) # Output: "A"Explanation of the Code:
- Base Case Check:
- If
numRowsis 1, return the stringsas it is because there is no zigzag pattern to form.
- If
- Initialize Rows:
- Create a list
rowswithmin(numRows, len(s))empty strings. This ensures that we have at most as many rows as the length of the string.
- Create a list
- Track Current Row and Direction:
- Use
cur_rowto keep track of the current row. - Use
going_downas a flag to indicate the direction of traversal (downwards or upwards).
- Use
- Iterate Over Characters:
- For each character in the string, append it to the current row.
- If the current row is the first or last row, toggle the
going_downflag to change direction. - Update
cur_rowto move to the next row (either up or down).
- Concatenate Rows:
- After processing all characters, concatenate all rows to form the final zigzag string.
Solution in Javascript:
JavaScript
/**
* @param {string} s
* @param {number} numRows
* @return {string}
*/
var convert = function(s, numRows) {
// If numRows is 1, return the string as is since there's no zigzag pattern
if (numRows === 1) {
return s;
}
// Initialize an array of strings for each row
let rows = new Array(Math.min(numRows, s.length)).fill("");
let curRow = 0;
let goingDown = false;
// Iterate over each character in the input string
for (let char of s) {
rows[curRow] += char;
// Change direction when you reach the top or bottom row
if (curRow === 0 || curRow === numRows - 1) {
goingDown = !goingDown;
}
// Move up or down in the rows
curRow += goingDown ? 1 : -1;
}
// Join all rows to get the final result
return rows.join("");
};
// Example usage:
console.log(convert("PAYPALISHIRING", 3)); // Output: "PAHNAPLSIIGYIR"
console.log(convert("PAYPALISHIRING", 4)); // Output: "PINALSIGYAHRPI"
console.log(convert("A", 1)); // Output: "A"Solution in Java:
Java
class Solution {
public String convert(String s, int numRows) {
// If numRows is 1, return the string as is since there's no zigzag pattern
if (numRows == 1) {
return s;
}
// Initialize a list of StringBuilder objects for each row
List<StringBuilder> rows = new ArrayList<>();
for (int i = 0; i < Math.min(numRows, s.length()); i++) {
rows.add(new StringBuilder());
}
int curRow = 0;
boolean goingDown = false;
// Iterate over each character in the input string
for (char c : s.toCharArray()) {
rows.get(curRow).append(c);
// Change direction when you reach the top or bottom row
if (curRow == 0 || curRow == numRows - 1) {
goingDown = !goingDown;
}
// Move up or down in the rows
curRow += goingDown ? 1 : -1;
}
// Join all rows to get the final result
StringBuilder result = new StringBuilder();
for (StringBuilder row : rows) {
result.append(row);
}
return result.toString();
}
// Main method for testing
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.convert("PAYPALISHIRING", 3)); // Output: "PAHNAPLSIIGYIR"
System.out.println(sol.convert("PAYPALISHIRING", 4)); // Output: "PINALSIGYAHRPI"
System.out.println(sol.convert("A", 1)); // Output: "A"
}
}Solution in C#:
C#
public class Solution {
public string Convert(string s, int numRows) {
// If numRows is 1, return the string as is since there's no zigzag pattern
if (numRows == 1) {
return s;
}
// Initialize an array of StringBuilder objects for each row
StringBuilder[] rows = new StringBuilder[Math.Min(numRows, s.Length)];
for (int i = 0; i < rows.Length; i++) {
rows[i] = new StringBuilder();
}
int curRow = 0;
bool goingDown = false;
// Iterate over each character in the input string
foreach (char c in s) {
rows[curRow].Append(c);
// Change direction when you reach the top or bottom row
if (curRow == 0 || curRow == numRows - 1) {
goingDown = !goingDown;
}
// Move up or down in the rows
curRow += goingDown ? 1 : -1;
}
// Join all rows to get the final result
StringBuilder result = new StringBuilder();
foreach (StringBuilder row in rows) {
result.Append(row);
}
return result.ToString();
}
}