6. ZigZag Conversion

he 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 text, int nRows);

convert("PAYPALISHIRING", 3)

should return

"PAHNAPLSIIGYIR"

Solution

(1) Java

public String convert(String s, int numRows) {
        if (s == null || s.length() == 0 || numRows == 1) {
            return s;
        }
        int length = s.length();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < numRows; i++) {
            int k = numRows-i-1;
            int j = i;
            int dir = 0;
            while (j < length) {
                sb.append(s.charAt(j)); 
                if (i == 0) {
                    j += k*2;
                } else if (i == numRows-1) {
                    j += i*2;
                } else {
                    if (dir%2==0) {
                        j += k*2;
                    } else {
                        j += i*2;
                    }
                }
                dir++;
            }
        } 
        return sb.toString();
    }

Although my solution has better performance, but it is error prone becaue some corner cases must be considered, the following solution is more straightforward and easy to code:

    public String convert(String s, int numRows) {
        int index = 0;
        StringBuilder[] st = new StringBuilder[numRows];
        for (int i = 0; i < st.length; i++) st[i] = new StringBuilder();
        while (index < s.length()) {
            for (int i = 0; i < numRows && index < s.length(); i++) st[i].append(s.charAt(index++));
            for (int i = numRows - 2; i > 0 && index < s.length(); i--) st[i].append(s.charAt(index++));
        }
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < st.length; i++) result.append(st[i]);
        return result.toString();
   }

(2) Python

def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        rows = [[] for _ in range(numRows)]
        idx = 0
        while idx < len(s):          
            for row in range(numRows):
                if idx < len(s):
                    rows[row].append(s[idx])
                    idx += 1
                else:
                    break
            for row in range(numRows-2, 0, -1):
                if idx < len(s):
                    rows[row].append(s[idx])
                    idx += 1
                else:
                    break
        ss = ["".join(row) for row in rows]
        rst = "".join(ss)
        return rst

The above code is still not optimized. We should think like this: using an idx to traverse all chars in s, so it keeps increasing, and using another variable row to move from 0->numRows-1->0->numRows-1. Do not think too complex:

def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if not s or numRows <= 1:
            return s
        rows = [""]*numRows
        idx, step, row = 0, 0, 0
        for idx in range(len(s)):
            row += step
            rows[row] += s[idx]
            if row == 0:
                step = 1
            elif row == numRows-1:
                step = -1
        return "".join(rows)

(3) Scala

Same algorithm, less code:

def convert(s: String, numRows: Int): String = {
        if (s.length() <= numRows || numRows <= 1) {
            return s
        }
        var row = 0
        var step = 0
        val rows = Array.fill[String](numRows)("")
        for (idx <- 0 until s.length()) {
            rows(row) += s(idx)
            if (row == 0) {
                step = 1
            } else if (row == numRows-1) {
                step = -1
            }
            row += step
        }
        return rows.reduceLeft(_ + _)
    }