LeetCode: ZigZag Conversion

The 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".

---

The naive idea for this problem is to use a string container to process the letter one by one. This will take O(n) time and O(n) space. Another solution is to compute the indices for letters in each row and this will take O(n) time and O(1) space.

C++ Code:

/*
 *func: zigzag_convert
 *goal: convert a string to zigzag pattern
 *@param s: the input string
 *@param nRows: the number of rows
 *return: the converted string
 */
/*
 *idea: use a vector of string to store each row
 *complexity: time O(n), space O(n)
 */
string zigzag_convert(const string &s, const int &nRows){
    assert(nRows > 0);
    //Corner Case, length of s is less than nRows or nRows is 1
    if(s.length() <= nRows || nRows == 1){
        return string(s);
    }
    
    vector<string> container(nRows);
    
    //indicator for going up or down
    bool going_up = false;
    int current_row = 0;
    
    for(int i = 0; i< s.length(); ++i){
        if(going_up){
            container.at(current_row).push_back(s[i]);
            
            //If reach the top, going down, else going up
            current_row == 0 ? ++current_row : --current_row;
            going_up = current_row == 0 ? false : true;
        }else{
            container.at(current_row).push_back(s[i]);
            
            //If reach the bottom, going up, else going down
            current_row == nRows-1 ? --current_row : ++current_row;
            going_up = current_row == nRows-1 ? true : false;
            
        }
    }
    
    //Construct the result
    string result = "";
    for(auto it = container.begin(); it != container.end(); ++it){
        result += *it;
    }
    
    return result;
}

/*
 *func: zigzag_convert
 *goal: convert a string to zigzag pattern
 *@param s: the input string
 *@param nRows: the number of rows
 *return: the converted string
 */
/*
 *idea: compute every index row by row
 *complexity: time O(n), space O(1)
 */
string zigzag_convert(const string &s, const int &nRows){
    assert(nRows > 0);
    //Corner Case, length of s is less than nRows or nRows is 1
    if(s.length() <= nRows || nRows == 1){
        return string(s);
    }
    
    string result;
    for(int i = 0; i < nRows; ++i){
        //Compute the index row by row
        //For the given example string "PAYPALISHIRING" and nRows = 3
        //output is
        //P   A   H   N   
        //A P L S I I G   
        //Y   I   R      
        //[0,0]->[0]            [0,1]->[4]            [0,2]->[8]             [0,3]->[12]
        //[1,0]->[1] [1,1]->[3] [1,2]->[5] [1,3]->[7] [1,4]->[9] [1,5]->[11] [1,6]->[13]
        //[2,0]->[2]            [2,1]->[6]            [2,2]->[10]
        //For those column with full elements, the index will be (nRows+nRows-2)*j + i where i
        //is the current row number and j is the current column number
        //For those column without full elements, the index will be index + (nRows-i-1)*2
        for(int j = 0, index = i; index < s.size(); ++j, index = (2*nRows-2)*j+i){
            //elements for full-element column
            result.push_back(s[index]);
            
            //There won't be element right behind for the first line and the last line
            if(i == 0 || i == nRows-1){
                continue;
            }
            
            if((index + (nRows-i-1)*2) < s.length()){
                result.push_back(s[index + (nRows-i-1)*2]);
            }
        }
    }
    
    return result;
}

Python Code:

#func: convert the current string to a zigzag pattern
#@param s: input string s
#@param nRows: number of rows
#@return: the converted string
#complexity: time O(n), space O(n)
def zigzag_convert(s, nRows):
    assert nRows > 0

    #Corner Case: if the length of s is lees than nRows or nRows is 1
    if len(s) <= nRows or nRows == 1:
        return s

    #Container
    container = []
    for _ in xrange(nRows):
        container.append('')

    #indicator for going up or down
    going_up = False

    current_row = 0

    for char in s:
        container[current_row]+=char
        if going_up:
            if current_row != 0:
                current_row -= 1
            else:
                current_row += 1
                going_up = False
        else:
            #Update current row and indicator
            if current_row != nRows-1:
                current_row += 1
            else:
                current_row -= 1
                going_up = True

    #concatenate string in container
    result = ''
    for string in container:
        result += string

    return result

#func: convert the current string to a zigzag pattern
#@param s: input string s
#@param nRows: number of rows
#@return: the converted string
#complexity: time O(n), space O(1)
def zigzag_convert(s, nRows):
    assert nRows > 0

    #Corner Case: if the length of s is lees than nRows or nRows is 1
    if len(s) <= nRows or nRows == 1:
        return s

    result = ''
    for i in xrange(nRows):
        #Compute the index row by row
        #For the given example string "PAYPALISHIRING" and nRows = 3
        #output is
        #P   A   H   N  
        #A P L S I I G  
        #Y   I   R     
        #[0,0]->[0]            [0,1]->[4]            [0,2]->[8]             [0,3]->[12]
        #[1,0]->[1] [1,1]->[3] [1,2]->[5] [1,3]->[7] [1,4]->[9] [1,5]->[11] [1,6]->[13]
        #[2,0]->[2]            [2,1]->[6]            [2,2]->[10]
        #For those column with full elements, the index will be (nRows+nRows-1)*j + i where i
        #is the current row number and j is the current column number
        #For those column without full elements, the index will be index + (nRows-i-1)*2

        #Current row index
        index = i
        #Current column index
        j = 0
        while index < len(s):
            result += s[index]

            #There won't be element right behind for the first line and the last line
            if i == 0 or i == nRows-1:
                j += 1
                index = (2*nRows-2)*j + i
                continue

            if (index + (nRows-i-1)*2) < len(s):
                result += s[(index + (nRows-i-1)*2)]

            j += 1
            index = (2*nRows-2)*j + i

    return result

---

Reference Link:

1.[LeetCode] ZigZag Conversion 解题报告: http://fisherlei.blogspot.com/2013/01/leetcode-zigzag-conversion.html