Skip to main content
title should say what code does
Source Link
dfhwze
  • 13.9k
  • 3
  • 38
  • 101

Does slicing in Comparing algorithms to decode a loop in Python slow down the time?String

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)\$O(n)\$ where n\$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.

Does slicing in a loop in Python slow down the time?

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.

Comparing algorithms to decode a String

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.

Source Link
Dawn17
  • 215
  • 1
  • 3

Does slicing in a loop in Python slow down the time?

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.