General solution with mathematical explanation and implementation in python


  • 0
    K

    This problem has a very simple and elegant mathematical solution. But to go there, let's do some visual analysis first. After we get our zigzagged string, let's try to assign character on each line to some list, like on the picture below,
    0_1472534117502_toarray.png
    Question is how to know beforehand which character goes to which list. In order to do so, let's put character indices as values on X axis and corresponding list indices on Y axis. For a given string (A1 ... A35) plot will look like as follows
    0_1472534586719_toplot.png
    You can immediately notice that it's a periodic function. In general that means that if you take the minimal part of the plot as below
    0_1472535092275_toplot1.png
    and shift right and left as infinitely many times you get all possible values of the function.
    0_1472535161095_toplot2.png
    In our case, period is 10. The blue segment of the plot is a simple function y = |x|. Now, how to find right red segment? According to the plot, we need to shift the red segment by 10, so it's y = |x - 10|, the next right segment would be y = |x - 20| and so forth. How to write it in a most general way? Obviously y = |x - 10k|, but the value of k depends on which segment you're on. You can easily guess that x values on each segment are bound by 10k - 5 ≤ x ≤ 10k + 5, or if you convert it k = 10 ⌊(x + 5)/10⌋
    You can also guess, that period 10 is actually connected to the number of rows as 2(numRows - 1).

    After you find that mapping, rest is the mere technicality of joining characters in each list and then joining again across all lists. To wrap it up, here's the python code

    class Solution(object):
        def convert(self, s, numRows):
            """
            :type s: str
            :type numRows: int
            :rtype: str
            """
            new_string = [[] for a in range(numRows)]
            period = (numRows - 1)*2
            for i, char in enumerate(s):
                new_string[abs(i - period*((i+period/2)//period))].append(char)
            return ''.join([''.join(a) for a in new_string])
    

    PS: beware, the code above won't pass all the test cases upon submission, since there's no checks for edge cases, like zero period or period being longer than two length of the string, etc.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.