yokostan / Leetcode-Solutions

Doing exercise on Leetcode. Carry on!
0 stars 3 forks source link

Leetcode #6 ZigZag Conversion #148

Open yokostan opened 5 years ago

yokostan commented 5 years ago

Build a StringBuilder[] with each row as a StringBuilder, then combine the StringBuilders into a whole String. Brilliant thought is that our pointer's row index goes from 0 to numRows - 1, then back to 0, one step at a time, so we can use index += incre and change the direction (1 or -1) at the edges. Here is the solution:

class Solution {
    public String convert(String s, int numRows) {
        if (numRows <= 1) {
            return s;
        }

        StringBuilder[] sb = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            sb[i] = new StringBuilder("");
        }

        int index = 0, incre = 1;
        for (int i = 0; i < s.length(); i++) {
            sb[index].append(s.charAt(i));
            if (index == 0) {
                incre = 1;
            }
            else if (index == numRows - 1) {
                incre = -1;
            }
            index += incre;
        }

        StringBuilder res = new StringBuilder();
        for (int i = 0; i < numRows; i++) {
            res.append(sb[i]);
        }

        return res.toString();
    }
}

Another brilliant solution utilizes StringBuffer[] data structure, which is the same as StringBuilder structure in this problem. Here we iterate vertically down then obliquely up using two adjacent iterations. Finally we append all other strings to sb[0] and return sb[0].toString() as our final result. Well, this saves some space.

class Solution {
    public String convert(String s, int numRows) {
        if (numRows <= 1) {
            return s;
        }

        StringBuilder[] sb = new StringBuilder[numRows];

        for (int i = 0; i < numRows; i++) {
            sb[i] = new StringBuilder();
        }

        for (int i = 0; i < s.length();) {
            for (int index = 0; index < numRows && i < s.length(); index++) {
                sb[index].append(s.charAt(i));
                i++;
            }
            for (int index = numRows - 2; index >= 1 && i < s.length(); index--) {
                sb[index].append(s.charAt(i));
                i++;
            }
        }

        for (int i = 1; i < numRows; i++) {
            sb[0].append(sb[i]);
        }

        return sb[0].toString();
    }
}