runtime 4 ms, beats 97.21% of cpp submissions
O(n) solution with explanation

tags: string, simulation

Zigzag Conversion

📖 description

給定一字串以及變數 row，將所有字元以特殊形式排列後，將排列後的字元以上到下、左到右的順序組合成新字串並回傳。

ex. s = “PAHNAPLSIIGYIR”, row = 3
將字串排成這樣

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

並按照順序組合成 “PAHNAPLSIIGYIR”

🧠 solution

最直接的想法是把一個2維陣列建出來，接著以 row 的順序組合，但這題可以避免這個步驟，只需要想像把整個2維陣列擠壓成類似底下這樣，在遍歷字串時決定好每個字元出現的在第幾個 row，就可以簡單的完成。

PAHN
APLSIIG
YIR

⏳ time complexity

遍歷一次字串 O(n) ，組合字串 O(row)
總時間複雜度 O(n)

📝 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
class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows==1) return s;
        int n = s.size();
        int cur = 0;
        vector<string> rows(numRows);       // 儲存每個 row
        bool down = true;                   // 當前要走的方向
        string ans;
        for(int i=0;i<n;i++){
            rows[cur] += s[i];
            if(down==true){                 // 如果目前要往下一個 row 走
                cur++;
            }
            else{
                cur--;                      // 在上升階段
            }
            if(cur==0 || cur==numRows-1){   // 到轉折點時切換方向
                down = !down;
            }
        }
        for(auto& row : rows){
            ans+=row;
        }
        return ans;
    }
};