[C++]Straight and easy way. O(n) both time and space complexity


  • 1
    Y

    Code First

    class Solution {
    public: 
    string convert(string s, int nRows) {
    	if (nRows <= 1) return s;
    	string str;
    	int pos = 0, len = s.length(), offset = 0;
    	for (int i = 0; i < nRows; i++){      //for each row, find the elements and add to string str
    		pos = i, offset = 2 * (nRows - 1 - i);                              
    		while (pos < len){                //which mean str = str + s[pos] 
    			str += s.substr(pos, 1);      
    			if (i != 0 && i != nRows - 1 && pos + offset < len)
                                 //if it's not the first or last line, we need add one more,
    				str += s.substr(pos + offset, 1);  //that is str = str + s[pos+offset]
    			pos += 2 * nRows - 2;
    		}
    	}
    	return str;
      }
    };
    

    First, read my comment in code line by line, you will understand my solution.

    Then, let me show you more detail.

    There is no doubt that there exist a pattern for each line.

    //this is a zigzag sample
    F          F          F       //First line
    *        * *        * *
    M1    M2   M3     M4         //Middle inle   
    *    *     *    *    
    *  *       *  *      
    L          L                 //Last line
    

    The first and last line of zigzag, each character are separated by 2 * (nRows - 1 ) chars in string s.

    Middle lines between 0 and nRows-1, characters showed in pairs, which mean we need add two characters into the string str once.

    In middle line showed above, M1 and M2 both need added to string str, and the distance in string s between M1 and M2 is exactly the same as M3, M4. The distance is the var offset in my code.

    offset = 2 * (nRows - 1 - i) life is so short, let's skip the proof

    The time complexity is O(n) undoubtedly, space as well.(n=s.length(), nothing to do with the nRows)


Log in to reply
 

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