CATEGORY: MEDIUM
Problem
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)
1 2 3 | P A H N A P L S I I G Y I R |
And then read line by line: “PAYPALISHIRING”
Write the code that will take a string and make this conversion given a number of rows:
1 | string convert(string s, int numRows); |
Examples
Example 1:
1 2 | Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR" |
Example 2:
1 2 3 4 5 6 7 | Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI" Explanation: P I N A L S I G Y A H R P I |
Example 3:
1 2 | Input: s = "A", numRows = 1 Output: "A" |
Constraints:
1 <= s.length <= 1000sconsists of English letters (lower-case and upper-case),','and'.'.1 <= numRows <= 1000
Solution Approach
In this problem of zigzag conversion, we must traverse the given string in the zigzag order and print the output string with letters in the rows consecutively.
We use the StringBuilder class to mutate the string to solve this problem of zigzag conversion. We have to traverse the string down and up, so we have to follow a 2-D matrix format. By following this format, we can travel the letters in words according to our requirements. If the number of rows given is one. Then we can directly return the given string. If the number of rows is greater than one, we can use either StringBuilder or List to solve this problem.
The time complexity of this approach is O(n) as we are traversing the matrix only once. The space complexity is also O(n) as we are using the space in form of StringBuilder or List to store the answer.
Initially, we have to create an array of StringBuilder of length equal to the number of rows. Later to traverse the string we define variables like length and index.
Firstly, we have to traverse down, for iteration we use for loop with the condition, i<number of rows and append the current character of the string to the StringBuilder array. Next, we have to fill the last second row and traverse up. So, we consider for loop with initialization i= number of rows -2 and iterate up to the first row and append the value to StringBuilder array. We have to continue these two steps until the character at the index is null. Thus, we initially start this traversal procedure with a while loop with a condition index less than the length of a string.
Finally, create a variable result and append the array and return the result. The return type is a string so we converted the result to a string using toString() method.
Solution Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | class Solution { public String convert(String s, int numRows) { StringBuffer[] array = new StringBuffer[numRows]; for (int i=0; i<numRows; i++){ array[i] = new StringBuffer(); } int length = s.length(); int index =0; while (index < length){ for(int i=0; i<numRows ;i++){ if(index >= length) break; array[i].append(s.charAt(index++)); } for(int i = numRows-2; i>0;i--){ if(index >= length) break; array[i].append(s.charAt(index++)); } } String Builder result = array[0]; for(int i=0;i<numRows;i++){ result.append(array[i].toString());} return result.toString(); |
For more Leetcode explained solutions visit Leetcode Solutions. If you like capture the flag challenges visit here.
Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via the Contact page. Happy Leetcoding 🙂