Solution by RoyLeo


  • 0
    R

    firstly, we find the law;

    for example,we have a string of length 10,and numRows = 4.
    0_1514044917180_1.png
    all we need to do is find the map {0,1,2,3,4,5,6,7,8,9} -> {0,1,2,3,2,1,0,1,2,3}
    the result string is periodic ,say,{0,1,2,3,2,1} ,the period is 6,and the law is :[ (numRows-1)*2 ]

    1. construct the base sequence: {0,1,...,numRows-1,numRows-2,...1}
      for vector "base" of length 2*(numRows-1) i:0- 2*(numRows-1)-1
      if i <= numRows-1 base[i] = i;
      else base[i] = 2*(numRows-1) -i; //symmetry

    2. In terms of periodicity,
      the char's index of string belong to which line is
      index = s[i % Size],where Size = 2*(numRows-1)
      this is the keypoint
      so we can use numRows string to store intermediate result

    3. merge every sring, we get result

    the cpp solution is as follows:
    ''''
    class Solution {
    public:
    string convert(string s, int numRows) {

    	int len = s.length();
    
    	if(numRows <= 0) return NULL;
    	if(len <= numRows) return s;
    	if(numRows == 1) return s;
    
    	//get base sequeue eg {0,1,2,3,2,1}
    	vector<int> base;
    	int Size = (numRows-1)*2;
    	assert( Size != 0);
    	for(int i = 0; i < Size ;++i)
    	{
    		if(i <= numRows-1) base.push_back(i);
    		else base.push_back(2*(numRows-1)-i);
    	}
    
    	//get answer
    	vector<vector<char>> res(numRows);
    	for(int i  = 0; i < len ;++i)
    	{
    		int index = base.at(i % (Size));
    		res[index].push_back(s.at(i));
    	}
    
    	//merge result
    	string dst;
    	for(int i = 0; i < numRows;++i)
    	{
    		int cnt = res[i].size();
    		for(int j = 0; j < cnt; ++j)
    		{
    			dst += res[i][j];
    		}
    	}
    	return dst;
    }
    

    };
    '''''''


Log in to reply
 

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