My simple and direct method with O(n) space and O(n) time


  • 1
    O

    I use nRows strings to make links ,use curr to decide which string to put in, use dir to control the curr move dirrection. Everytime the curr reaches the edge, change dirrection. Then connect each string to make the zigzag string.

    class Solution {
    public:
        string convert(string s, int nRows) {
            int curr=0,dir=nRows==1?0:-1;
            vector<string> links(nRows);
            for(int i=0;i<s.size();i++)
            {
                links[curr].push_back(s[i]);
                if(curr==0||curr==nRows-1) dir*=-1;
                curr+=dir;
            }
            string ret;
            for(int i=0;i<links.size();i++) ret+=links[i];
            return ret;
        }
    };

Log in to reply
 

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