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