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 string convert(string s, int numRows) to transform the string into the specified number of rows.

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 use a two-dimensional string array to record (later proved unnecessary, the two-dimensional string array can be directly replaced with a string type list)

2. There are two directions in the 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 line by line.

Let numRows be the number of rows, and let the strings in each row be s1, s2, … , s**n. It is easy to find that when traversing the string s in order, the row index of each character c in the N pattern first increases from s1 to s**n, and then decreases from s**n 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:#

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 row index corresponding to the current character c;
3. flag = - flag: Reverse when reaching the turning point of the N pattern.

,,,,,,,,

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 strings in each row 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();
    }
}