LeetCode 6. ZigZag Conversion

一、     问题描述：

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

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 conversiongiven a number of rows:

string convert(string s, int numRows);

Example1:

Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR"

Example2:

Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI" Explanation:   P     I    N A   L S  I G Y A   H R P     I

 

二、     问题分析:

    首先确定ZigZagConversion（Z字转换）的定义：将给定的字符串根据行数先转换为示例所展示的Z形结构，最后将其逐行读取构成新的字符串。

以example 1为例子：

    输入字符串为"PAYPALI SHIRING", 行数为3，所以列出的Z形结构为：

    P   A  H   N

    A P L S I I G

    Y   I   R

    逐行读取方式：  

    

    所以输出的字符串就应为："PAHNAPLSIIGYIR"

 

三、     算法设计：

    1、 假定给定字符串为S，行数为rows

    2、 因为要根据所给的字符串罗列出Z形结构，Z形结构可以看成一个二维字符数组（空白看成是空字符‘’）；

    3、 因为构造行已知但列未知的二维数组很难实现，所以可以等价构造出目的二维矩阵的转置矩阵E；

    4、 定义行计数变量num =0、b=0，遍历字符串S，执行以下操作：

        a)     若行b为0，即第一行，则将E[num]整行填充rows个字符；

        b)     若行b不为0，则对应的将E的第num行第rows-b-1个元素，即E[num][rows-b]填充字符，其余元素填充空字符

        c)      b = b+1, num = num+1

    5、 对E按行优先进行字符串遍历，获得的字符串即为目的字符串

 

四、     程序实现：

class Solution: def convert(self, s, numRows): """ :type s: str :type numRows: int :rtype: str """ s = list(s) arr = [] h = 0 num = 0 a = 0 newstr = [] while(num < len(s)): row = ['' for a in range(numRows)] if(a==0 or a==numRows-1): for b in range(numRows): if(num < len(s)): row[b] = s[num] num+=1 else: row[numRows-1-a] = s[num] num += 1 a = (a + 1)%numRows if(a==numRows-1): a = 0 h += 1 arr.append(row) for a in range(numRows): for b in range(h): if(arr[b][a]!=''): newstr.append(arr[b][a]) return ''.join(newstr)