Leetcode 06
Published:
Z字形变换
Z字形变换 [medium]
将一个给定字符串根据给定的行数，以从上往下、从左到右进行Z字形排列。
Example
1.
输入: s = "LEETCODEISHIRING", numRows = 3
L C I R
E T O E S I I G
E D H N
输出: "LCIRETOESIIGEDHN"
2.
输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:
L D R
E O E I I
E C I H N
T S G
思路
从左到右迭代 ss，将每个字符添加到合适的行。
只有当我们向上移动到最上面的行或向下移动到最下面的行时，当前方向才会发生改变。
时间复杂度：O(n), 其中n=len(s)
空间复杂度：O(n)
Solution
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1 || numRows >= s.length()){
return s;
}
List<StringBuilder> rows = new ArrayList<>();
for (int i = 0; i < numRows; i++)
rows.add(new StringBuilder());
int curRow = 0;
boolean goingDown = false;
for (char c : s.toCharArray()) {
rows.get(curRow).append(c);
if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
curRow += goingDown ? 1 : -1;
}
StringBuilder ret = new StringBuilder();
for (StringBuilder row : rows) ret.append(row);
return ret.toString();
}
}