Difficulty: Medium#
Problem:#
Arrange a given string s
in a zigzag pattern and read it line by line.
For example, if the input string is "PAYPALISHIRING" and the number of rows is 3, the arrangement is as follows:
P A H N
A P L S I I G
Y I R
Afterwards, you need to read it line by line from left to right to generate a new string, such as: "PAHNAPLSIIGYIR".
Please implement the function string convert(string s, int numRows)
to transform the string into the specified number of rows.
Example:#
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"
Analysis:#
Personal analysis:#
-
Convert the inverted Z to a regular Z, and use a two-dimensional string array to record (later proved unnecessary, the two-dimensional string array can be directly replaced with a string type list)
-
There are two directions in the traversal, one with i unchanged and j++, and the other with i++, j-- (later in the official solution, flag=1, -1 is used to represent these two states, which is more elegant)
Official analysis:#
The string s
is stored in a zigzag pattern, and the goal is to print it line by line.
Let numRows
be the number of rows, and let the strings in each row be s1, s2, … , s**n. It is easy to find that when traversing the string s
in order, the row index of each character c
in the N pattern first increases from s1 to s**n, and then decreases from s**n to s1... This is repeated.
Therefore, the solution is to simulate the change of this row index, and fill each character c
in s
into the correct row res[i]
during traversal.
Algorithm:#
Traverse the string s
in order:
res[i] += c
: Fill each characterc
into the corresponding row s**i;i += flag
: Update the row index corresponding to the current characterc
;flag = - flag
: Reverse when reaching the turning point of the N pattern.
Code:#
- [Python]
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows < 2: return s
res = ["" for _ in range(numRows)]
i, flag = 0, -1
for c in s:
res[i] += c
if i == 0 or i == numRows - 1: flag = -flag
i += flag
return "".join(res)
- [Java]
class Solution {
public String convert(String s, int numRows) {
if(numRows < 2) return s;
List<StringBuilder> rows = new ArrayList<StringBuilder>();
for(int i = 0; i < numRows; i++) rows.add(new StringBuilder());
int i = 0, flag = -1;
for(char c : s.toCharArray()) {
rows.get(i).append(c);
if(i == 0 || i == numRows -1) flag = - flag;
i += flag;
}
StringBuilder res = new StringBuilder();
for(StringBuilder row : rows) res.append(row);
return res.toString();
}
}
- [C++]
class Solution {
public:
string convert(string s, int numRows) {
if (numRows < 2)
return s;
vector<string> rows(numRows);
int i = 0, flag = -1;
for (char c : s) {
rows[i].push_back(c);
if (i == 0 || i == numRows -1)
flag = - flag;
i += flag;
}
string res;
for (const string &row : rows)
res += row;
return res;
}
};
Complexity analysis:#
- Time complexity *O*(*N*): Traverse the string
s
once; - Space complexity *O*(*N*): The strings in each row occupy a total of O(N) additional space.
Personal code:#
class Solution {
public String convert(String s, int numRows) {
if (numRows < 2) {
return s;
}
ArrayList<StringBuilder> rows = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
rows.add(new StringBuilder());
}
int flag = -1;
int i = 0;
for (char c : s.toCharArray()) {
if (i == 0 || i == numRows - 1) {
flag = -flag;
}
rows.get(i).append(c);
i += flag;
}
StringBuilder res = new StringBuilder();
rows.forEach(e->res.append(e));
return res.toString();
}
}