cropper or striver

Difficulty: Medium#

Problem:#

Arrange a given string s in a zigzag pattern and read it line by line.

For example, if the input string is "PAYPALISHIRING" and the number of rows is 3, the arrangement is as follows:

P A H N
A P L S I I G
Y I R
Afterwards, you need to read it line by line from left to right to generate a new string, such as "PAHNAPLSIIGYIR".

Please implement the function to convert the string into the specified number of rows:

string convert(string s, int numRows);

Example:#

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"

Analysis:#

Personal analysis:#

1. Convert the inverted Z to a regular Z, and then use a two-dimensional string array to record (later proved unnecessary, a two-dimensional string array can be directly replaced with a list of string types)

2. There are two directions for traversal, one with i unchanged and j++, and the other with i++, j-- (later in the official solution, flag=1, -1 is used to represent these two states, which is more elegant)

Official analysis:#

The string s is stored in a zigzag pattern, and the goal is to print it row by row.

Let s1, s2, ..., sn be the strings in numRows rows, it is easy to find that: when traversing the string s in order, the row index corresponding to each character c in the N-shaped pattern first increases from s1 to sn, and then decreases from sn to s1... This is repeated.

Therefore, the solution is to simulate the change of this row index, and fill each character c in s into the correct row res[i] during traversal.

Algorithm process:#

Traverse the string s in order:

1. res[i] += c: Fill each character c into the corresponding row s[i];
2. i += flag: Update the current row index corresponding to the character c;
3. flag = - flag: When reaching the turning point of the N-shaped pattern, execute the reverse.

,,,,,,,,

Code:#

• [Python]

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows < 2: return s
        res = ["" for _ in range(numRows)]
        i, flag = 0, -1
        for c in s:
            res[i] += c
            if i == 0 or i == numRows - 1: flag = -flag
            i += flag
        return "".join(res)

• [Java]

class Solution {
    public String convert(String s, int numRows) {
        if(numRows < 2) return s;
        List<StringBuilder> rows = new ArrayList<StringBuilder>();
        for(int i = 0; i < numRows; i++) rows.add(new StringBuilder());
        int i = 0, flag = -1;
        for(char c : s.toCharArray()) {
            rows.get(i).append(c);
            if(i == 0 || i == numRows -1) flag = - flag;
            i += flag;
        }
        StringBuilder res = new StringBuilder();
        for(StringBuilder row : rows) res.append(row);
        return res.toString();
    }
}

• [C++]

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows < 2)
            return s;
        vector<string> rows(numRows);
        int i = 0, flag = -1;
        for (char c : s) {
            rows[i].push_back(c);
            if (i == 0 || i == numRows -1)
                flag = - flag;
            i += flag;
        }
        string res;
        for (const string &row : rows)
            res += row;
        return res;
    }
};

Complexity analysis:#

• Time complexity *O*(*N*): Traverse the string s once;
• Space complexity *O*(*N*): The rows of strings occupy a total of O(N) additional space.

Personal code:#

class Solution {
    public String convert(String s, int numRows) {
        if (numRows < 2) {
            return s;
        }
        ArrayList<StringBuilder> rows = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            rows.add(new StringBuilder());
        }
        int flag = -1;
        int i = 0;
        for (char c : s.toCharArray()) {
            if (i == 0 || i == numRows - 1) {
                flag = -flag;
            }
            rows.get(i).append(c);
            i += flag;
        }

        StringBuilder res = new StringBuilder();
        rows.forEach(e->res.append(e));
        return res.toString();
    }
}