[LeetCode] 6. ZigZag Conversion

轉自LeetCode

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
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 text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

<Solution>

這題不難，直接用 zigzag 的方式去存每個 row 該有的字元，也是會過

但時間就是跑得比較久

更快的方式，是去觀察 zigzag 排法和原本 index 的位置關係 (參考資料)

首先，下圖是 zigzag 的排序方式

接著，用 "0123456789ABCDEF" 這個字串來舉例

下圖是用 zigzag 排法 (numRows  = 4) 之後的樣子

可以觀察到兩件事

• 首(row = 0) 和尾(row = 3) 是沒有斜線部分的元素
• 不在斜線上的元素，他們在 string 裡面的 index  關係是間隔 2*numRows - 2

來計算一下

字元6 :  0 + ( 2 * 4 - 2) = 6

字元7 :  1 + ( 2 * 4 - 2) = 7

字元8 :  2 + ( 2 * 4 - 2) = 8

字元F :  9 + ( 2 * 4 - 2) = 15

因此，對於每個 row，只要按間隔 2*numRows - 2，就能找到所有不在斜線上的字元

接著看斜線上的元素

可以觀察出來， index = prvIdx + interval - 2 * row

prvIdx : 上一個在同row但不在斜線上的字元的 index

interval : 2*numRows - 2

row : 目前要找個字元所在的 row

來計算一下

字元5 :  1 + (2 * 4 - 2) - 2 * 1 = 5

字元A : 8 + (2 * 4 - 2) - 2 * 2 = 10

綜合上述觀察，把它寫成 code 就可以了

	class Solution {
	public:
	string convert(string s, int numRows) {
	if(s.length() == 0) {
	return "";
	}
	else if(numRows == 1) {
	return s;
	}
	string ans = "";
	int interval = 2 * numRows - 2;
	for(int i = 0; i < numRows; i++) { //> row
	for(int j = i; j < s.length(); j += interval) {
	//> j is the index of element on the vertical line
	ans += s[j];
	//> there are no adjacent elements when row = 0 and row = numRows -1
	if(i != 0 && i != (numRows - 1)) {
	int tmpIdx = j + interval - 2 * i;
	if(tmpIdx < s.length()) {
	ans += s[tmpIdx];
	}
	}
	}
	}
	return ans;
	}
	};

view raw zigzag.cpp hosted with ❤ by GitHub