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)
And then read line by line: "PAHNAPLSIIGYIR"
Constraints
Approach
Links
YouTube
Examples
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Explanation:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
Solutions
/**
* Time complexity :
* Space complexity :
*/
class Solution {
public String convert(String s, int numRows) {
if(s.length() == 1 || numRows <= 1) return s;
int row = 0;
int n = s.length();
boolean down = true;
String[] arr = new String[n];
Arrays.fill(arr, "");
for(int i = 0; i < n; i++) {
arr[row] += s.charAt(i);
if(row == numRows-1) {
down = false;
} else if(row == 0) {
down = true;
}
if(down) {
row++;
} else {
row--;
}
}
return String.join("", arr);
}
}
/**
* Time complexity :
* Space complexity :
*/
class Solution {
public String convert(String s, int numRows) {
if(s.length() == 1 || numRows <= 1) return s;
int row = 0;
int n = s.length();
boolean down = false;
String[] arr = new String[numRows];
Arrays.fill(arr, "");
for(char ch: s.toCharArray()) {
arr[row] += ch;
if(row == numRows-1 || row == 0) down = !down;
row += (down ? 1: -1);
}
return String.join("", arr);
}
}
/**
* Time complexity :
* Space complexity :
*/
class Solution {
public String convert(String s, int numRows) {
int n = s.length();
if(n == 1 || numRows <= 1 || numRows > n) return s;
int interval = (2 * numRows) - 2;
StringBuilder sb = new StringBuilder();
for(int i = 0; i < numRows; i++) {
int step = interval - (2 * i);
for(int j = i; j < n; j += interval) {
sb.append(s.charAt(j));
if(step > 0 && step < interval && (j+step) < n) {
sb.append(s.charAt(j+step));
}
}
}
return sb.toString();
}
}
