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 RAnd 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
