Z Font conversion

subject

Will a given string $s$ According to the given number of rows $numRows$ , From top to bottom 、 Left to right Z Font arrangement .
For example, the input string is "PAYPALISHIRING" The number of rows is 3 when , Arranged as follows ：

after , Your output needs to be read line by line from left to right , Generate a new string , such as ：“PAHNAPLSIIGYIR”.

Please implement this function to transform a string into a specified number of lines ：

string convert(string s, int numRows);

Example

Method 1 ： Analog transformation process

Analysis topic , take Z The glyph is regarded as a two-dimensional matrix , The process of transformation is simply described as ： Fill the characters in the string into the two-dimensional matrix in turn , The filling order is from [0][0] Start to go down , fill numRows That's ok , And then according to [ Row number -1][ Number of columns +1] Fill in one character at a time , until Row number =0, Then fill in , fill numRows After that, follow [ Row number -1][ Number of columns +1] Fill in one character at a time , Cycle until all the characters in the string are filled , Finally, the final string is sorted out in the way of line reading .

Realization way

Use one Vector Container to store the elements of each row , The final Z Glyph total numRows That's ok , So first initialize a containing numRows An element of Vector, according to Z The order of font transformation , Put the second in turn i Put the characters of the line into Vector No i Of the elements , In the end Vector The strings in each element of the are spliced into the final result .

Set an index vIndex stay [0,numRows-1] Move back and forth between , Indicates the number of rows of the current character in the two-dimensional matrix , The characters in the string are added to Vector No vIndex Of the elements .

Code implementation

class Solution {
    
public:
    string convert(string s, int numRows) {
    
      // Used to traverse the string  s  The index of 
      int index = 0;
      int size = s.length();
    
      if (numRows == 1 || numRows >= size) {
    
        cout << s << endl;
        return 0;
      }
      
      vector<string> nRes(numRows, "");
      //vIndex Used to point to the number of rows of the current element in the two-dimensional matrix , The same is Vector The element index of 
      int vIndex = 0;
      // Judge whether the current row index should be increased or decreased 
      bool add = true;
      
      while (index < size)
      {
    
        // From 0 Fill in  numRows  Elements 
        while (index < size && add) {
    
          nRes[vIndex] += s[index];
          vIndex++;
          index++;
          if (vIndex == numRows) {
    
            add = false;
          }
        }
        vIndex -= 2;
        // according to  [ Row number -1][ Number of columns +1]  Fill in one character at a time , until   Row number =0
        while (!add && index < size) {
    
          nRes[vIndex] += s[index];
          vIndex--;
          index++;
          if (vIndex == -1) {
    
            add = true;
          }
        }
        vIndex += 2;
      }
      string res = "";
      for (string var : nRes)
      {
    
        res += var;
      }
      return res;
};

Read the solution on Li Kou , Also found the law of transformation , And use mathematical formulas to express , The idea is similar to , Can be used as a reference .