Description

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)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string s, int numRows);

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

Submission

I visit the characters by row and divided the characters into cycles, and inside each cycle, there are 2 cases, when it is in the boundary rows and when it is in between. For boundary rows, only 1 character appear in a single cycle, and the index is (rowIndex + cycleIndex * charsInCycle), while the charsInCycle is easily calculated and represented in the program below as T. For non-boundary rows, 2 letters appear in a single cycle, so 2 variables i1 and i2 are maintained and use one after the other in each cycle.

class Solution {
    public String convert(String s, int numRows) {
        StringBuilder sb = new StringBuilder();
        // int index = 0;
        int T = (numRows - 1) * 2;
        
        if(numRows == 1) return s;
        
        for(int row = 0; row < numRows; row++) {
            if(row == 0 || row == numRows - 1) {
                for(int i = row; i < s.length(); i += T) {
                    sb.append(s.charAt(i));
                }
            } else {
                boolean changeT = true;
                for(int i1 = row, i2 = 2 * numRows - row - 2; 
                    (changeT && i1 < s.length()) || (!changeT && i2 < s.length()); 
                    changeT = !changeT) {
                    int i = changeT ? i1 : i2;
                    
                    sb.append(s.charAt(i));
                    
                    if(!changeT) {
                        i1 += T;
                        i2 += T;
                    }
                    
                }
            }
        }
        return sb.toString();
    }
}

Solution

My submission above is called “Visit by Row”, another way to solve this problem is Sort by Row, it costs much more space(O(N)), but illustrates another strategy also in O(N) in terms of time complexity.

This method is like playing a game on the map, each character in the String s tries to find the correct place for itself. The crux is to find out the right conditions to change the “walk vector” on the “map”.

class Solution {
    public String convert(String s, int numRows) {

        if (numRows == 1) return s;

        List<StringBuilder> rows = new ArrayList<>();
        for (int i = 0; i < Math.min(numRows, s.length()); 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();
    }
}