#!/usr/bin/python
# -*- encoding=utf-8 -*- s
# 文件名：leetcode0006.py

import time

def performance(f):
    def fn(*args, **kw):
        t1 = time.time()
        r = f(*args, **kw)
        t2 = time.time()
        print 'call %s() in %fs' % (f.__name__, (t2-t1))
        return r
    return fn


class Solution(object):
    """
    将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
    比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
    L   C   I   R
    E T O E S I I G
    E   D   H   N
    之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
    请你实现这个将字符串进行指定行数变换的函数：
    string convert(string s, int numRows);
    
    示例 1:
    输入: s = "LEETCODEISHIRING", numRows = 3
    输出: "LCIRETOESIIGEDHN"

    示例 2:
    输入: s = "LEETCODEISHIRING", numRows = 4
    输出: "LDREOEIIECIHNTSG"
    解释:
    L     D     R
    E   O E   I I
    E C   I H   N
    T     S     G
    """
    @performance
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        def initL(numRows):
            L = []
            for i in range(numRows):
                tmp = []
                L.append(tmp)
            return L

        if (numRows == 1):
            return s

        L = initL(numRows)
        j = 0
        flage = True
        for i in range(len(s)):
            #print "i:%d, j:%d" % (i, j)
            L[j].append(s[i])
            if flage:
                j += 1
                if j == numRows - 1:
                    flage = False
            else:
                j -= 1
                if j == 0:
                    flage = True
        dst = ''
        for i in range(numRows):
            dst += ''.join(L[i])
        return dst


if __name__ == '__main__':
    solution = Solution()
    print solution.convert('LEETCODEISHIRING', 4)

