3
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Doesn't slicing take O(j - i) in S[i:j]? \$\endgroup\$ – Dawn17 Aug 30 '19 at 6:46
  • \$\begingroup\$ @Dawn17, yes it does. However, in the worst case each character gets handled twice (e.g. consider a string that has an enormous number of digits and then one letter). O(2n) is still O(n). \$\endgroup\$ – RootTwo Aug 30 '19 at 20:22

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.