[Leetcode] 6. Zigzag Conversion

6. Zigzag Conversion

• Hardness: \(\color{orange}\textsf{Medium}\)
• Ralated Topics: String

一、題目

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to dispaly this pattern in a fixed font for better legibility)
\( \quad\texttt{P A H N}\\ \quad\texttt{APLSIIG}\\ \quad\texttt{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

Example 1:

• Input: s = “PAYPALISHIRING”, numRows = 3
• Output: “PAHNAPLSIIGYIR”

Example 2:

• Input: s = “PAYPALISHIRING”, numRows = 3
• Output: “PINALSIGYAHRPI”
• Explanation:
  \( \quad\texttt{P　I　N}\\ \quad\texttt{A LS IG}\\ \quad\texttt{YA HR}\\ \quad\texttt{P　I}\\ \)

Example 3:

• Input: s = “A”, numRows = 1
• Output: “A”

Constraints:

• 1 <= s.length <= 1000
• s consists of English letters (lower-case and upper-case), ',' amd '.'.
• 1 <= numRows <= 1000>

二、分析

• 創建 numRows 個 vectors，依照，用一個 k 控制當下的字元要放到哪一個 vector 中。
• 用一個 unit 來控制 k 要往上走還是往下走。
• 按照規律，當 k + unit 為 numRows 與 -1 時，unit 要正負翻轉。
• 特例：當 numRows 等於 1 時，輸出等於輸入。

三、解題

1. Array

• Time complexity: \(O(n)\)
• Space complexity: \(O(n)\)

string convert(string s, int numRows) {
    if (numRows == 1) return s;
    vector<string> rows(numRows);
    int unit = 1;
    int k = 0;
    for (int i = 0; i < s.length(); i++) {
        if (k + unit == numRows || k + unit == -1)
            unit *= -1;
        rows[k].push_back(s[i]);
        k += unit;
    }
    
    string res;
    for (string& s : rows) res += s;
    return res;
}

回目錄 Catalog