題目連結:
題目意譯:
字串 "PAYPALISHIRING" 以「之字形」的方式寫在給定的列數上,如下(你可能會想要將下列圖示以等寬字型來表示,以確保易讀性):
P A H N
A P L S I I G
Y I R
接著一列一列讀得到:"PAHNAPLSIIGYIR"
撰寫一份程式碼,其將把給定的字串並在給定的列數下以上述形式轉換成另一字串:
string convert(string s, int numRows);
限制:
1 ≦ s.length ≦ 1000
s 由英文字母(小寫和大寫)、',' 和 '.' 所組成。
1 ≦ numRows ≦ 1000
範例測資:
範例 1:
輸入: s = "PAYPALISHIRING", numRows = 3
輸出: "PAHNAPLSIIGYIR"
範例 2:
輸入: s = "PAYPALISHIRING", numRows = 4
輸出: "PINALSIGYAHRPI"
解釋:
P I N
A L S I G
Y A H R
P I
範例 3:
輸入: s = "A", numRows = 1
輸出: "A"
解題思維:
首先,如果 numRows 恰好為 1,則答案就是 s 本身。
反之,我們可以看到實際上不需要真的形成「之字形」。例如範例 2 的
P I N
A L S I G
Y A H R
P I
可以去掉空白得到
PIN
ALSIG
YAHR
PI
然後從上至下串接起來依舊可以得到原本的答案。
因此我們只需要宣告出 numRows 個空字串。然後就直接從第一個字串開始依序把 s 的每一個字母放到第一個、第二個、 ……這些字串的尾端,然後碰到第 numRows 個字串就回頭放在第 numRows - 1 個、第 numRows - 2 個、……直到回到第一個字串。然後就重複這個步驟直到 s 中的字母都放完為止。
最後把每一個字串串接起來便可以得到所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。