6. Zigzag Conversion
https://leetcode.com/problems/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 <= 1000sconsists of English letters (lower-case and upper-case),','and'.'.1 <= numRows <= 1000
---
Intuition
Concatenate characters sequentially into each row
Create placeholder StringBuilder for each row
Create min (s.length(), numRows) stringBuilder list -- account for corner case
track direction - down or up
increment or decrement row depending on direction
Combine all row StringBuilders into final answer
---
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public String convert(String s, int numRows) { | |
| // Corner cases | |
| if (numRows < 2 || s == null || s.length() < 2) { | |
| return s; | |
| } | |
| int row = 0; | |
| boolean down = false; | |
| List<StringBuilder> rows = new ArrayList<StringBuilder>(); | |
| // List of stringbuilders to collect characters in each row | |
| for (int i = 0; i < Math.min(numRows, s.length()); i++) { | |
| rows.add(new StringBuilder()); | |
| } | |
| // Append character to respective row | |
| for (char c: s.toCharArray()) { | |
| rows.get(row).append(c); | |
| // reverse direction on boundary | |
| if (row == 0 || row == numRows - 1) { | |
| down = !down; | |
| } | |
| // increment or decrement row | |
| row += down ? 1 : -1; | |
| } | |
| // Builder result with stringbuilders from each row | |
| StringBuilder ans = new StringBuilder(); | |
| for (StringBuilder iter: rows) { | |
| ans.append(iter); | |
| } | |
| return ans.toString(); | |
| } | |
| } |
