String
Description
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 R
And 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 s, int numRows);
Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"
Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I
Example 3:
Input: s = "A", numRows = 1
Output: "A"
Constraints:
1 <= s.length <= 1000
s
consists of English letters (lower-case and upper-case), ','
and '.'
.
1 <= numRows <= 1000
Solutions
Solution 1: Simulation
We use a two-dimensional array $g$ to simulate the process of the $Z$-shape arrangement, where $g[i][j]$ represents the character at the $i$-th row and the $j$-th column. Initially, $i=0$, and we define a direction variable $k$, initially $k=-1$, indicating moving upwards.
We traverse the string $s$ from left to right. Each time we traverse to a character $c$, we append it to $g[i]$. If $i=0$ or $i=numRows-1$ at this time, it means that the current character is at the turning point of the $Z$-shape arrangement, and we reverse the value of $k$, i.e., $k=-k$. Next, we update the value of $i$ to $i+k$, i.e., move up or down one row. Continue to traverse the next character until we have traversed the string $s$, and we return the string concatenated by all rows in $g$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the string $s$.
Python3 Java C++ Go TypeScript Rust JavaScript C#
1
2
3
4
5
6
7
8
9
10
11
12 class Solution :
def convert ( self , s : str , numRows : int ) -> str :
if numRows == 1 :
return s
g = [[] for _ in range ( numRows )]
i , k = 0 , - 1
for c in s :
g [ i ] . append ( c )
if i == 0 or i == numRows - 1 :
k = - k
i += k
return '' . join ( chain ( * g ))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 class Solution {
public String convert ( String s , int numRows ) {
if ( numRows == 1 ) {
return s ;
}
StringBuilder [] g = new StringBuilder [ numRows ] ;
Arrays . setAll ( g , k -> new StringBuilder ());
int i = 0 , k = - 1 ;
for ( char c : s . toCharArray ()) {
g [ i ] . append ( c );
if ( i == 0 || i == numRows - 1 ) {
k = - k ;
}
i += k ;
}
return String . join ( "" , g );
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 class Solution {
public :
string convert ( string s , int numRows ) {
if ( numRows == 1 ) {
return s ;
}
vector < string > g ( numRows );
int i = 0 , k = -1 ;
for ( char c : s ) {
g [ i ] += c ;
if ( i == 0 || i == numRows - 1 ) {
k = - k ;
}
i += k ;
}
string ans ;
for ( auto & t : g ) {
ans += t ;
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 func convert ( s string , numRows int ) string {
if numRows == 1 {
return s
}
g := make ([][] byte , numRows )
i , k := 0 , - 1
for _ , c := range s {
g [ i ] = append ( g [ i ], byte ( c ))
if i == 0 || i == numRows - 1 {
k = - k
}
i += k
}
return string ( bytes . Join ( g , nil ))
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 function convert ( s : string , numRows : number ) : string {
if ( numRows === 1 ) {
return s ;
}
const g : string [][] = new Array ( numRows ). fill ( 0 ). map (() => []);
let i = 0 ;
let k = - 1 ;
for ( const c of s ) {
g [ i ]. push ( c );
if ( i === numRows - 1 || i === 0 ) {
k = - k ;
}
i += k ;
}
return g . flat (). join ( '' );
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 impl Solution {
pub fn convert ( s : String , num_rows : i32 ) -> String {
let num_rows = num_rows as usize ;
if num_rows == 1 {
return s ;
}
let mut ss = vec! [ String :: new (); num_rows ];
let mut i = 0 ;
let mut to_down = true ;
for c in s . chars () {
ss [ i ]. push ( c );
if to_down {
i += 1 ;
} else {
i -= 1 ;
}
if i == 0 || i == num_rows - 1 {
to_down = ! to_down ;
}
}
let mut res = String :: new ();
for i in 0 .. num_rows {
res += & ss [ i ];
}
res
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 /**
* @param {string} s
* @param {number} numRows
* @return {string}
*/
var convert = function ( s , numRows ) {
if ( numRows === 1 ) {
return s ;
}
const g = new Array ( numRows ). fill ( _ ). map (() => []);
let i = 0 ;
let k = - 1 ;
for ( const c of s ) {
g [ i ]. push ( c );
if ( i === 0 || i === numRows - 1 ) {
k = - k ;
}
i += k ;
}
return g . flat (). join ( '' );
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 public class Solution {
public string Convert ( string s , int numRows ) {
if ( numRows == 1 ) {
return s ;
}
int n = s . Length ;
StringBuilder [] g = new StringBuilder [ numRows ];
for ( int j = 0 ; j < numRows ; ++ j ) {
g [ j ] = new StringBuilder ();
}
int i = 0 , k = - 1 ;
foreach ( char c in s . ToCharArray ()) {
g [ i ]. Append ( c );
if ( i == 0 || i == numRows - 1 ) {
k = - k ;
}
i += k ;
}
StringBuilder ans = new StringBuilder ();
foreach ( StringBuilder t in g ) {
ans . Append ( t );
}
return ans . ToString ();
}
}
Solution 2
Python3 Java C++ Go TypeScript Rust JavaScript PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 class Solution :
def convert ( self , s : str , numRows : int ) -> str :
if numRows == 1 :
return s
group = 2 * numRows - 2
ans = []
for i in range ( 1 , numRows + 1 ):
interval = group if i == numRows else 2 * numRows - 2 * i
idx = i - 1
while idx < len ( s ):
ans . append ( s [ idx ])
idx += interval
interval = group - interval
if interval == 0 :
interval = group
return '' . join ( ans )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 class Solution {
public String convert ( String s , int numRows ) {
if ( numRows == 1 ) {
return s ;
}
StringBuilder ans = new StringBuilder ();
int group = 2 * numRows - 2 ;
for ( int i = 1 ; i <= numRows ; i ++ ) {
int interval = i == numRows ? group : 2 * numRows - 2 * i ;
int idx = i - 1 ;
while ( idx < s . length ()) {
ans . append ( s . charAt ( idx ));
idx += interval ;
interval = group - interval ;
if ( interval == 0 ) {
interval = group ;
}
}
}
return ans . toString ();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 class Solution {
public :
string convert ( string s , int numRows ) {
if ( numRows == 1 ) return s ;
string ans ;
int group = 2 * numRows - 2 ;
for ( int i = 1 ; i <= numRows ; ++ i ) {
int interval = i == numRows ? group : 2 * numRows - 2 * i ;
int idx = i - 1 ;
while ( idx < s . length ()) {
ans . push_back ( s [ idx ]);
idx += interval ;
interval = group - interval ;
if ( interval == 0 ) interval = group ;
}
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 func convert ( s string , numRows int ) string {
if numRows == 1 {
return s
}
n := len ( s )
ans := make ([] byte , n )
step := 2 * numRows - 2
count := 0
for i := 0 ; i < numRows ; i ++ {
for j := 0 ; j + i < n ; j += step {
ans [ count ] = s [ i + j ]
count ++
if i != 0 && i != numRows - 1 && j + step - i < n {
ans [ count ] = s [ j + step - i ]
count ++
}
}
}
return string ( ans )
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 function convert ( s : string , numRows : number ) : string {
if ( numRows === 1 ) {
return s ;
}
const ss = new Array ( numRows ). fill ( '' );
let i = 0 ;
let toDown = true ;
for ( const c of s ) {
ss [ i ] += c ;
if ( toDown ) {
i ++ ;
} else {
i -- ;
}
if ( i === 0 || i === numRows - 1 ) {
toDown = ! toDown ;
}
}
return ss . reduce (( r , s ) => r + s );
}
impl Solution {
pub fn convert ( s : String , num_rows : i32 ) -> String {
let num_rows = num_rows as usize ;
let mut rows = vec! [ String :: new (); num_rows ];
let iter = ( 0 .. num_rows ). chain (( 1 .. num_rows - 1 ). rev ()). cycle ();
iter . zip ( s . chars ()). for_each ( | ( i , c ) | rows [ i ]. push ( c ));
rows . into_iter (). collect ()
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 /**
* @param {string} s
* @param {number} numRows
* @return {string}
*/
var convert = function ( s , numRows ) {
if ( numRows == 1 ) return s ;
const arr = new Array ( numRows );
for ( let i = 0 ; i < numRows ; i ++ ) arr [ i ] = [];
let mi = 0 ,
isDown = true ;
for ( const c of s ) {
arr [ mi ]. push ( c );
if ( mi >= numRows - 1 ) isDown = false ;
else if ( mi <= 0 ) isDown = true ;
if ( isDown ) mi ++ ;
else mi -- ;
}
let ans = [];
for ( const item of arr ) {
ans = ans . concat ( item );
}
return ans . join ( '' );
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 class Solution {
/**
* @param string $s
* @param int $numRows
* @return string
*/
function convert($s, $numRows) {
if ($numRows == 1 || strlen($s) <= $numRows) {
return $s;
}
$result = '';
$cycleLength = 2 * $numRows - 2;
$n = strlen($s);
for ($i = 0; $i < $numRows; $i++) {
for ($j = 0; $j + $i < $n; $j += $cycleLength) {
$result .= $s[$j + $i];
if ($i != 0 && $i != $numRows - 1 && $j + $cycleLength - $i < $n) {
$result .= $s[$j + $cycleLength - $i];
}
}
}
return $result;
}
}