LeetCode 006 ZigZag Conversion

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

题目大意：

给定字符串按如上的“Z”字锯齿形进行按行重排。

解题思路：

这是一个周期性的字符串。周期是竖+折（不含首节点）。

首节点和竖的最后一点在每周期只会出现一次，其他点会出现两次。
T=2×numRows-2(因为不含竖节点最后一点+折线上的最后一点属于另一个周期)。nT是有几个周期，即使不完成的周期也算一个。
按行遍历（实质是周期上的每个点），再按周期遍历，非顶点有两个需加入到结果中：j×T+i,(j+1)×T-i。由于周期可能不完成，只要写一个API检查边界且加入字符即可。

注意事项：

一个字符的字符串。此时T=0.直接返回原字符串。

Java代码：

public String convert2(String s, int numRows) {
	StringBuffer sb = new StringBuffer();
	int T = numRows*2-2;
	if(T==0)
		return s;
	int nT = (int)Math.ceil((s.length()+0.0)/T);
	for(int i=0;i<numRows;i++){
		for(int j=0;j<nT;j++){
			if(i==0 || i==numRows-1)
				sb.append(addChar(s, j*T+i));
			else{
				sb.append(addChar(s, j*T+i));
				sb.append(addChar(s, (j+1)*T-i));
			}
		}
	}
	return sb.toString();
}

public String addChar(String s, int index){
	String a = "";
	if(index<s.length())
		return s.substring(index, index+1);
	return a;
}

算法分析：

时间复杂度为O(n)，空间复杂度O(1)。