My C++ solution O(N+Row)


  • 0
    P
    class Solution {
    public:
       string convert(string s, int nRows) {
          if (nRows == 1)
          {
             return s;
          }
          if (nRows < 1)
          {
             return nullptr;
          }
    
    // Calculating matrix column size.   
          size_t len = s.length();
          size_t rest = (len - 1) % (2 * (nRows - 1));
          if (rest <= (nRows - 1))
          {
             rest = 1;
          }
          else
          {
             rest = rest - (nRows - 1) + 1;
          }
          size_t col_factor = (len - 1) / (2 * (nRows - 1));
          size_t columns = (nRows - 1) * col_factor + rest;
          char** tMatrix;
          tMatrix = new char*[nRows];
          int a = 0;
    // Initialize
          for (; a < nRows; a++)
          {
             tMatrix[a] = new char[columns];
             for (size_t b = 0; b < columns;++b)
             {
                tMatrix[a][b] = ' ';
             }
          }
    // placing characters
          int p = 0;  // position
          int k = 0, j = 0;
          for (; p < static_cast<int>(len); ++p)
          {
             tMatrix[k][j] = s.c_str()[p];
             if ((p % (2 * (nRows - 1))) < (nRows - 1))
             {
                k++;
             }
             else
             {
                k--;
                j++;
             }
          }
    //Output 
          string ret;
          for (k = 0; k < nRows; ++k)
          {
             for (j = 0; j < static_cast<int>(columns); ++j)
             {
                if(tMatrix[k][j]!=' ') ret.append({ tMatrix[k][j] });
             }
          }
          for (a=0; a < nRows; a++)
          {
             delete[] tMatrix[a];
          }
          delete[] tMatrix;
          return ret;
       }
    };

Log in to reply
 

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