Solution by awice


  • 0

    Approach #1: Simulation [Accepted]

    Intuition

    We translate to code the steps a human would take to create the string.

    Algorithm

    For each letter in the string, we place that letter in the correct row cur_row, then move our pointer to the next correct row. We will need to know not only the location of our pointer, but it's current direction cur_direction: 1 for down and -1 for up.

    Care must also be taken in the case that numRows is 1.

    Python

    class Solution(object):
        def convert(self, S, numRows):
            rows = [[] for _ in range(numRows)]
            cur_row = 0
            cur_direction = 1
            
            for char in S:
                rows[cur_row].append(char)
                cur_row += cur_direction
                if cur_row == numRows:
                    cur_row = max(numRows - 2, 0)
                    cur_direction *= -1
                elif cur_row == -1:
                    cur_row = min(numRows - 1, 1)
                    cur_direction *= -1
                    
            return "".join("".join(row) for row in rows)
    

    Complexity Analysis

    • Time Complexity: $$O(N)$$, where $$N$$ is the length of the string. We loop through every character in the string and do constant work inside the loop.

    • Space Complexity: $$O(N)$$ to hold the answer, which has size proportional to the initial string.


    Approach #2: Index Generator [Accepted]

    Intuition

    Because knowing what row the next letter goes in is tricky, we write a helper generator that returns these indices.

    Algorithm

    We proceed as before: we will loop through the string and place the characters in rows. The index that we place it will be given by a generator.

    The generator is straightforward: if there are N rows, we go from 0 to N-1, then from N-2 to 1, then start over.

    Python

    class Solution(object):
        def convert(self, S, numRows):
            rows = [[] for _ in range(numRows)]
            def staircase_indexes(N):
                while True:
                    for i in range(N):
                        yield i
                    for i in range(N-2, 0, -1):
                        yield i
    
            gen_index = staircase_indexes(numRows)
            for c in S:
                rows[next(gen_index)].append(c)
    
            return "".join("".join(row) for row in rows)
    

    Complexity Analysis

    • $$O(n)$$ time and space complexity. The analysis is the same as in Approach #1.

    Approach #3: Mathematical [Accepted]

    Intuition

    For each row, let's try to know mathematically which string indices are going to be taken.

    Algorithm

    Say there are N rows. When N > 1, there are 2N-2 indices in the loop: 0, 1, ..., N-2, N-1, N-2, ..., 1 before the pattern of row indices repeats again. In the first and last row, we have string indices (zero-indexed) $$0 \mod 2N-2$$ and $$N-1 \mod 2N-2$$. In other rows $$i$$, we have string indices $$i$$ and $$2N-2-i$$.

    Python

    class Solution(object):
        def convert(self, S, N):
            if N == 1:
                return S
            
            ans = []
            for row in range(N):
                if row == 0 or row == N-1:
                    ans.append(S[row::2*N-2])
                else:
                    for i in range(0, len(S), 2*N-2):
                        for j in (i + row, i + 2*N-2-row):
                            if j < len(S):
                                ans.append(S[j])
                                
            return "".join(ans)
    

    Complexity Analysis

    • $$O(n)$$ time and space complexity. The analysis is the same as in Approach #1.

Log in to reply
 

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