My o(n) c++ solution, without extra space.


  • 0
    S
    class Solution {
    public:
    	string convert(string s, int numRows) {
    		if (numRows == 1)	return s;
    		string res;
    		int cellNum = numRows * 2 - 2;
    
    		for (int i = 0; i < numRows; i++){
    			int j = i;
    			int step = cellNum - 2 * i;
    			while (j < s.size()){
    				res += s[j];
    				if (step == 0 || step == cellNum)
    					j += cellNum;
    				else{
    					j += step;
    					if (j >= s.size())
    						break;
    					res += s[j];
    					j += (cellNum - step);
    				}
    			}
    		}
    		return res;
    	}
    };

Log in to reply
 

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