6.Zigzag Conversion

This question on LeetCode was so interesting that I initially tried to find a pattern or rule to solve it. However, after an hour of unsuccessful attempts, I decided to write an easy and straightforward solution that I came up with. Later on, I discovered this Youtube video, which presents a more elegant and cleaner solution.

Question

Solution 1

First, we initialize each item in the StringBuilder array and then we obtain the result through the following steps.

1. Loop for only one vertical line chars
2. Get back to the start row of diagonal line(like P)
3. Loop for only one diagonal line chars

Continue to repeat these steps until the loop reaches the last index of s.
This diagram illustrates how the steps progress.

// O(n)
class Solution {
    public String convert(String s, int numRows) {
        if(numRows == 1) {
            return s;
        }
        StringBuilder[] strs = new StringBuilder[numRows];
        for(int i=0; i<numRows; i++) {
            strs[i] = new StringBuilder();
        }
                
        int i = 0;
        while(i < s.length()) {
            int currRow = 0;
            //step 1. Loop for only one vertical line chars
            while(currRow < numRows && i < s.length()) {
                strs[currRow++].append(s.charAt(i++));
            }

            //step 2. Get back to the start row of diagonal line(like P)
            currRow -= 2;

            //step 3. Loop for only one diagonal line chars
            while(currRow > 0 && i < s.length()) {
                strs[currRow--].append(s.charAt(i++));
            }
        }

        StringBuilder res = new StringBuilder();
        for(StringBuilder str : strs) {
            res.append(str);
        }

        return res.toString();
    }
}

Solution 2 (Master)

Reference from Youtube video.

class Solution {
    public String convert(String s, int numRows) {
        if(numRows == 1) {
            return s;
        }
        int len = s.length();
        String ans = "";
        int i = 0;
        while(i < numRows) {
            int increment = 2*(numRows-1);
            int j = i;
            while(j < len){
                ans += s.charAt(j);
                if(i>0 && i<numRows-1 && j + increment - 2*i < len) {
                    ans += s.charAt(j + increment - 2*i);
                }
                j += increment;
            }
            i++;
        }
        return ans;
    }
}