6. Zigzag Conversion

LeetCode
,

My Solution (2D Array)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1 || s.length() <= numRows) return s;
        int length = s.length();
        char[] ch = s.toCharArray();
        int[][] text = new int[numRows][length];
        int[] pointer = new int[numRows];
        int current_row = 0;
        boolean goingDown = false;
        // store
        for (int i = 0; i < length; i++) {
            text[current_row][pointer[current_row]] = ch[i];
            pointer[current_row]++;
            
            if (current_row == 0 || current_row == numRows - 1) {
                goingDown = !goingDown;
            }
            current_row += goingDown ? 1 : -1;
        }
        // output
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < pointer[i]; j++) {
                result.append((char) text[i][j]); // 强转回 char
            }
        }
        return result.toString();

    }
}

Remarks:

  1. If only one row, directly return the original s
  2. Use goingDown to mark the direction

Builder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1 || s.length() <= numRows) return s;

        // Prepare a StringBuilder for each line
        StringBuilder[] rows = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            rows[i] = new StringBuilder();
        }

        int currentRow = 0;
        boolean goingDown = false;

        for (char c : s.toCharArray()) {
            rows[currentRow].append(c);

            if (currentRow == 0 || currentRow == numRows - 1) {
                goingDown = !goingDown; // go back
            }

            currentRow += goingDown ? 1 : -1;
        }

        // combine all lines
        StringBuilder result = new StringBuilder();
        for (StringBuilder row : rows) {
            result.append(row);
        }

        return result.toString();
    }
}

Remarks:

  1. Use StringBuilder instead of arrays, which helps to save memory and time

Index

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) {
        if (numRows == 1 || s.length() <= numRows) return s;

        StringBuilder result = new StringBuilder();
        int cycleLen = 2 * numRows - 2;

        for (int row = 0; row < numRows; row++) {
            for (int j = 0; j + row < s.length(); j += cycleLen) {
                result.append(s.charAt(j + row));  // 主列字符

                // 非首尾行还会有一个斜线字符
                int second = j + cycleLen - row;
                if (row != 0 && row != numRows - 1 && second < s.length()) {
                    result.append(s.charAt(second));
                }
            }
        }

        return result.toString();
    }
}
1
2
3
4
r0:    0       6       12 ...
r1:      1   5   7   11 ...
r2:        2 4     8 10 ...
r3:          3       9 ...