6. 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 s, int numRows);

Example 1:

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

Example 2:

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

Example 3:

Input: s = "A", numRows = 1
Output: "A"

Constraints:

• 1 <= s.length <= 1000
• s consists of English letters (lower-case and upper-case), ',' and '.'.
• 1 <= numRows <= 1000

解决思路

观察上面的例子，我们发现最后的输出是第一行的字母加上第二行的字母，一直加到最后一行的字母。那我们就考虑是不是可以建立numRows个临时空字符串，我们只要将字符串s中的每个字符，正确的插入到所在行对应的临时字符串的中，最后将这numRows个临时字符串拼接返回就可以了。

比如以上面那个示例为例，numRows=4，应该建立4个临时空字符串，L是第一个字符，则应该加入到第一个临时字符串中，E是第二个字符，应该加入到第二个临时字符串中，…，C是第五个字符，应该加入到第三个临时字符串中，…，一直到最后一个字符G加入到了第四个临时字符串中，最终将这四个临时字符串拼接到一起，则为我们需要的输出结果。

那我们问题的关键就变成了，如何确定字符串s中的每个字符所对应的行数，也就是说字符串s中的字符应该加入到第几个临时字符串中。

我们观察上面的两个示例，我们看看能不能发现如何确定字符对应行数的方法。

如上图所示，我们可以发现，进行Z字排列的时候，我们总是先向下排列numRows个字符，再从左向右从下到上排列numRows-2个字符，接下来，循环往复，直到我们最终完成所有字符的排列。则我们可以把排列的过程看成一个一个块的堆叠，即先排满前一个块之后才能排列下一个块，那么我们就可以很容易的找出每个字符所对应的行数。

思路1

根据我们上面的分析，我们排列字符串s中的字符的时候，是一个块一个块的进行排列，那我们可以得到，当一个块填满的时候，其容量为2*numRows-2。后面块中字符与第一个块对应位置的字符相差n个（2*numRows-2）的大小，那我们可以设置一个字典，确定第一个块中字符所在的行数，则后面所有的块的内容，可以通过减去n*(2*numRows-2)来映射到我们的字典中，获得其所在的行数。

我们可以写出完成的代码为：

class Solution:
    def convert(self, s, numRows):
        if numRows <= 1:
            return s

        n = 2*numRows-2
        temp_str = ['']*numRows
        temp_dict = {
    }

        for t in range(n):
            if t>=0 and t<numRows:
                temp_dict[t] = t
            else:
                temp_dict[t] = n-t
        
        for i in range(len(s)):
            temp_str[temp_dict[i%n]] += s[i]

        return ''.join(temp_str)

结果 80ms 时间复杂度O(n)

思路二 ¹

继续回到刚刚的分析过程，我们将排列的过程变成了一个一个块的填充，我们在填充一个块的时候，先向下排numRows个，然后再向上排列numRows-2个。

向下排是从第0行一直排到第numRows-1行，即可以用for j in range(numRows)表示

向上排列的过程可以看成一个倒序排列的过程，我们注意到倒序排列时，起始行是第numRows-2行(第numRows02行填充)，结束位置是第0行(第0行不填充)，则start=numRows-2，end=0，step=-1，则倒序排列为for k in range(numRows-2,0,-1)

这样对于一个块中的字符的填充我们就解决了，先for j in range(numRows)，再for k in range(numRows-2,0,-1)，后续块与这个块采用同样的方法便可以解决

如果上面的没搞清楚，看了下面的代码可以很快的搞明白了：

class Solution:
    def convert(self, s, numRows):
        if not numRows > 1:
            return s
        if numRows == 2:   #做了一个特例处理
            return s[::2]+s[1::2]

        temp_str = ['']*numRows
        i = 0
        n = len(s)
        while i < n:
            for j in range(numRows):
                if i < n:
                    temp_str[j] += s[i]  
                    i += 1
       
            for k in range(numRows - 2, 0, -1):  
                if i < n:
                    temp_str[k] += s[i]
                    i += 1
        return ''.join(temp_str)

结果 64ms 时间复杂度O(n)

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        print(s)
        print(numRows)
        if len(s) <= 1 or numRows == 1:
            return s
        
        n = numRows * 2 - 2

        tmp_dict = {}
        tmp_str = [''] * numRows

        for i in range(n):
            if i >=0 and i < numRows:
                tmp_dict[i] = i
            else:
                tmp_dict[i] = n - i
        print(tmp_dict)
        m = len(s)
        for j in range(m):
            print(j)
            print(j % n)
            tmp_row_index = tmp_dict[j % n]
            print(tmp_row_index)
            tmp_str[tmp_row_index] += s[j]
            print("-------------------")

        return ''.join(tmp_str)