LeetCode ZigZag Conversion

LeetCode ZigZag Conversion

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".


估计大多数人看到这题都不知道Zigzag具体是怎样一个pattern,题目也只给了一个例子,不好找规律,这是维基百科上介绍Zigzag时给的一张图片:

也就是先下后上来回走两条路径,下去和上来的路径是各自平行的。这一题中,下去是竖直下去的,上来是45°斜着走上来的。使用数组模拟走路过程即可。

代码如下:

class Solution {
public:
	string convert(string s, int numRows) {
		int n = s.size();
		if (numRows >= n || numRows == 1)
			return s;
		vector<vector<char>> board(numRows);
		int k = 0, i = 0;
		bool up = false;
		while (k < n)
		{
			board[i].push_back(s[k]);
			if (i >= numRows - 1)
				up = true;
			else if (i <= 0)
				up = false;
			if(up)
				i--;
			else
				i++;
			k++;
		}
		string ret = "";
		for (int i = 0; i < numRows; i++)
			for (int j = 0; j < board[i].size(); j++)
					ret += board[i][j];
		return ret;
	}
};

本代码提交AC,用时48MS。

Leave a Reply

Your email address will not be published. Required fields are marked *