Posts ZigZag Conversion
Post
Cancel

ZigZag Conversion

PROBLEM 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)

1
2
3
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);

leetcode

SOLUTION

NeetCode YouTube

snapshot

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution {
    
    public String convert(String s, int numRows) {

        //edge case
        if(numRows == 1) return s;

        //length of the string
        int n = s.length();

        //number of jumps to go to next character in the next group
        int jumps = 2*(numRows-1);

        //ans
        StringBuffer sb = new StringBuffer();

        //first row
        //it will start from index 0
        int i = 0;

        //while there are more characters, keep jumping 2*(numRows-1) times to go to next character in the next section of first row
        while(i<n){
            sb.append(s.charAt(i));
            i += jumps;
        }

        //rows in between
        //loop through the rows from [1, numRows-2]
        for(int row=1; row<=numRows-2; row++){
            
            //first character of row x, will be at index x
            i = row;

            //while there are more characters in the string
            while(i<n){
                
                //append the current character
                sb.append(s.charAt(i));

                //Important Part:
                //the next character in this row will be present at: currentIndex + 2*(numRows-1) - (2 * currentRow)
                int j = i + jumps - (2*row);

                //check if that index is within the bounds
                if(j<n){
                    sb.append(s.charAt(j));
                }

                //jump to the next character of the next group
                i += jumps;

            }

        }

        //last row (similar to first row)
        //the first character will be at numRows-1
        i = numRows-1;
        while(i<n){
            sb.append(s.charAt(i));
            i += jumps;
        }

        return sb.toString();


    }

}

ANOTHER WAY TO CODE

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {

    public String convert(String s, int numRows) {

        //edge case
        if(numRows == 1) return s;

        //length of the string
        int n = s.length();

        //number of jumps needed to go to next character (of next group)
        int jumps = 2 * (numRows-1);

        //ans
        StringBuffer sb = new StringBuffer();

        //for each row
        for(int r=0; r<numRows; r++){
            
            //the first character position for row x will be at x index of the string
            for(int i=r; i<n; i+=jumps){

                //append the current character of the row
                sb.append(s.charAt(i));
                
                //if it's a middle row, we will need to get the second character
                //it will be present at: currentIndex + 2*(numRows-1) - (2*currentRow)
                if(r >= 1 && r <= numRows-2){
                    
                    int secondCharPossiblePosition = i + jumps - (2*r); //this can possibly be out of bounds

                    //if it's within the bounds, append it
                    if(secondCharPossiblePosition < n){
                        sb.append(s.charAt(secondCharPossiblePosition));
                    }

                }

                //because of for loop increment condition, the next position will be current + 2*(numRows-1);

            }

        }

        return sb.toString();

    }

}
This post is licensed under CC BY 4.0 by the author.