2
\$\begingroup\$

This snippet uses a string as an output. As we iterate through the input string, I just keep appending a character to the string and I know this just pretty much creates a new string everything I add a new character since strings are immutable in Python.

def snake_string(s):
    res = ''
    for i in range(1, len(s), 4):
        res += s[i]
    for j in range(0, len(s), 2):
        res += s[j]
    for k in range(3, len(s), 4):
        res += s[k]
    return res

This uses a list as the output structure and use join to return a string at the end:

def snake_string(s):
    result = []
    # Outputs the first row, i.e., s[1], s[5], s[9], ...
    for i in range(1, len(s), 4):
        result.append(s[i])
    # Outputs the second row, i.e., s[0], s[2], s[4], ...
    for i in range(0, len(s), 2):
        result.append(s[i])
    # Outputs the third row, i.e., s[3], s[7], s[11], ...
    for i in range(3, len(s), 4):
        result.append(s[i])
    return ''.join(result)

I wonder how these two implementations differ in time and space complexity and which one a better way to do. I feel like the second one is better in terms of space because it just initializes on the list and keeps adding a new character to it, but I assume that the join at the end will cause another \$O(N)\$ time. Is this correct?

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.