LeetCode-6. ZigZag Conversion

[ninehills]

20170717

问题

https://leetcode.com/problems/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".

思路

1. 第一种思路是初始化一个矩阵，然后根据之字形去填充这个矩阵，最后转换为字符串输出。时间复杂度为O(n)
2. 改进措施是没必要填充这个矩阵，因为空的元素没有意义，仅仅是分行append即可

解答

class Solution(object):
    def convert(self, s, numRows):
        """方案1
        :type s: str
        :type numRows: int
        :rtype: str
        """
        matrix = []
        for i in range(numRows):
            matrix.append([])
        row = 0
        row_add = 1
        column = 0
        for i in s:
            #print 'row: {0}'.format(row)
            #print 'column: {0}'.format(column)
            if column >= len(matrix[row]):
                matrix[row] = matrix[row] + [None] * (column - len(matrix[row]) + 1)
            matrix[row][column] = i
            if numRows == 1:
                row_add = 0
            else:
                if row == 0:
                    row_add = 1
                if row == numRows - 1:
                    row_add = -1
            row = row + row_add
            if row_add == -1 or row_add == 0:
                column = column + 1
                
        
        ret = ""
        #print matrix
        for r in matrix:
            for i in r:
                if i != None:
                    ret += i
        return ret
    def convert2(self, s, numRows):
        """方案2，更加精妙，来自于讨论区"""
        step = (numRows == 1) - 1  # 0 or -1  
        rows, idx = [''] * numRows, 0
        for c in s:
            rows[idx] += c
            if idx == 0 or idx == numRows-1: 
                step = -step  #change direction  
            idx += step
        return ''.join(rows)

# "PAHNAPLSIIGYIR"       
print Solution().convert("PAYPALISHIRING", 3)
# "AB"       
print Solution().convert("AB", 1)
# "ABC"       
print Solution().convert("AB", 1)