Question

P   A   H   N
A P L S I I G
Y   I   R

string convert(string text, int nRows);

Approach

Intuition

If we want to output the result by reading line by line, we need to know the index of the each character. So how to find the specific index sequence of the characters which are read line by line is what we focus on mainly.

Algorithm

Now we will try to resolve the problem as follow:

Firstly, we get the string s, such as “ABCDEFGHIJKLMNO…”, and the three row ns, each equals 3, 4 and 5, as shown below:

• n = 3

A     E     I  
B  D  F  H  J
C     G     K

• n = 4

A        G       M
B     F  H    L  N
C  E     I  K    O
D        J       P

• n = 5

A         I         Q
B      H  J      P  R
C    G    K    O    S
D  F      L  N      T
E         M         U

Secondly, we need to find the index sequence while reading line by line. Obviously, the indexes of the first line are what as follow:

• 0, 4, 8 for n = 3;
• 0, 6, 12 for n = 4;
• 0, 8, 16 for n = 5.

Because:

• For the n = 3 case, the index of the A character equals 0, E equals 4, I equals 8;
• For the n = 4 case, the index of the A character equals 0, G equals 6, M equals 12;
• For the n = 5 case, the index of the A character equals 0, I equals 8, Q equals 16;

Now, we could get the conclusion that for the first line, the distance of numbers adjacent to each other is 2(n -1). So the index for the kth(k = 0, 1, 2…) element of the ith line could be expressed by expression that 2 * k (n - 1) + i

Then, we could also get the same conclusion for the nth line, because the nth line is similar to the 0th line.

Then, for the other lines(the 1th to the n - 1th lines)， the difference between the 0th or nth line case is that there is one more character, and the indexes of those are shown as follow:

For the n = 4 case

• The 2th line, the F character’s index equals 5, L equals 11;
• The 3th line, the E character’s index equals 4, K equals 10;

So we could find the one more character’s index is 2 * i (i is the current line number, such as 0, 1, 2, 3…) less then the next number’s.

Now, we could get the conclusion that for the 1th to n - 1th lines, the index for the kth(k = 0, 1, 2…) element of the ith line could be expressed by expression that:

• for the k % 2 == 0 case, the is similar to the 0th or nth line, so the index is k * (n - 1) + i
• for the k % 2 != 0 case, the index is 2 * i less then the next element’s. The next element’s index is (k + 1) * (n - 1) + i, so the index of the current character which is before the next element is (k + 1) * (n - 1) + i - 2 * i, we get the expression that (k + 1) * (n - 1) - i;

Finally, the index of the characters which are read line by line c_i can be expressed as follow:

[code lang=”cpp”]
if (i == 0 || i == n – 1) {
c_i = 2 * k * (n – 1) + i;
} else {
c_i = (k % 2 == 0) ? k * (n – 1) + i : (k + 1) * (n – 1) – i;
}
[/code]

C++

class Solution {
public:
    string convert(string s, int n) {
            int l = s.length(), k = 0, c_i = 0;
            string r_s = ""; 
            if (n == 1) return s;
            for (int i = 0; i < n; ++i) {
                while(true) {
                    if (i == 0 || i == n - 1) c_i = 2 * k * (n - 1) + i;
                    else c_i = (k % 2 == 0) ? k * (n - 1) + i : (k + 1) * (n - 1) - i;
                    if (c_i >= l) break;
                    r_s.append(s, c_i, 1); 
                    ++k;
                }   
                k = 0;
            }   
            return r_s;
    }
};

Complexity Analysis

• Time complexity : O(n). The n is the length of the original string.

To calculate all the characters’ index, we need to scan all of them. Thus, it costs O(n) time.

• Space complexity : O(n). The extra space required for storing the characters in String as well as returning them.