Comparing algorithms to decode a String

Question

I am writing a function to decode a string, which means performing a string transformation like 3e4f2e --> eeeffffee.

I have two versions of codes which are very similar but slightly different. In version1,

def decoding(s):
    res = []
    curr = 0
    curr_val = 0
    while curr < len(s):
        if not s[curr].isdigit():
            res.append(curr_val * s[curr])
            curr_val = 0
        else:
            curr_val = curr_val * 10 + int(s[curr])
        curr += 1
    return ''.join(res)

I keep in track of curr_val and keep accumulating the value until I see a non-digit string.

In version2, I keep in track of the first position of the digit string and slice the string just to represent the digit string.

def decoding(s):
    digit_start, res = 0, []
    curr = 0
    while curr < len(s):
        if not s[curr].isdigit():
            res.append(int(s[digit_start:curr]) * s[curr])
            digit_start = curr + 1
        curr += 1
    return ''.join(res)

I just keep in track of the right index and multiply the int of that string with the current non-digit string (e.g. 10a --> aaaaaaaaaa)

I wonder if the first version has a way better time complexity or if they have the same time complexity in big-O. I assumed that both of them are \$O(n)\$ where \$n\$ is the length of the input string, but I wonder if slicing inside a loop would significantly increase the time-complexity of the code.

Please note that this is an interview practice, so I care about time-complexity, not the real-world style.

Answer 1

They both look like they are \$O(n)\$.

A quick check with timeit show they both take essentially the same amount of time, and the time grows linearly with the length of the input string.

It would be better to iterate over the characters in the string rather use an explicit index over the length of the string (while curr < len(s) is often a smell).

def decoding(s):
    result = []
    repeat = 0

    for c in s:
        if c.isdigit():
            repeat = 10 * repeat + int(c)

        else:
            result.append(repeat * c)
            repeat = 0

    return ''.join(result)

or:

def decoding(s):
    result = []
    prev_index = 0

    for index,c in enumerate(s):
        if not c.isdigit():
            result.append(int(s[prev_index:index]) * c)
            prev_index = index + 1

    return ''.join(result)