6. Zigzag Conversion

• Time: $O(|\texttt{s}|)$
• Space: $O(|\texttt{s}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: string convert(string s, int numRows) { string ans; vector> rows(numRows); int k = 0; int direction = (numRows == 1) - 1; for (const char c : s) { rows[k].push_back(c); if (k == 0 || k == numRows - 1) direction *= -1; k += direction; } for (const vector& row : rows) for (const char c : row) ans += c; return ans; } }; 
  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) { StringBuilder sb = new StringBuilder(); List[] rows = new List[numRows]; int k = 0; int direction = numRows == 1 ? 0 : -1; for (int i = 0; i < numRows; ++i) rows[i] = new ArrayList<>(); for (final char c : s.toCharArray()) { rows[k].add(c); if (k == 0 || k == numRows - 1) direction *= -1; k += direction; } for (List row : rows) for (final char c : row) sb.append(c); return sb.toString(); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution: def convert(self, s: str, numRows: int) -> str: rows = [''] * numRows k = 0 direction = (numRows == 1) - 1 for c in s: rows[k] += c if k == 0 or k == numRows - 1: direction *= -1 k += direction return ''.join(rows)