In fact, this is a math problem, JAVA code.


  • 5
    F
    public String convert(String s, int numRows) {
        if (numRows <= 1) {
            return s;
        }
        int n = s.length();
        int step = 2 * numRows - 2;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < numRows; i++) {
            for (int j = i; j < n; j += step) {
                sb.append(s.charAt(j));
                if (i != 0 && i != numRows - 1 && j + step - 2 * i < n) {
                    sb.append(s.charAt(j + step - 2 * i));
                }
            }
        }
        return sb.toString();
    }

  • 0
    Y

    Good idea! I have almost the exact same logic but got memory limit exceed just because I left out the case when numRows == 1. Do you know why so?


  • 0
    F

    when numRows==1, step==0, the second for loop won't work, notice j+=step, j wont increase, the following algorithm will fail, so we take numRows==1 as a special case


  • 0
    I

    This is the best solution. Efficient and easy to digest.

    See my c++ version

    class Solution {
    public:
        string convert(string s, int numRows) {
            if(1==numRows){
                return s;
            }
            int N=s.size();
            string result(s);
            int p=0;
            int steps = 2*numRows-2;
            int lastRowIdx=numRows-1;
            for(int i=0;i<numRows;i++){
                for(int j=i;j<N;j+=steps){
                    result[p++]=s[j];
                    if(i>0 && i<lastRowIdx){
                        int jj = j+(lastRowIdx-i)*2;
                        if(jj<N) result[p++]=s[jj];
                    }
                }
            }
            return result;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.