-
Notifications
You must be signed in to change notification settings - Fork 7
/
uncompress_v2.py
57 lines (47 loc) · 2.95 KB
/
uncompress_v2.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
def uncompress(s):
"""
Decodes a compressed string based on a simple format.
The compressed string uses the following format:
- A character followed by a number represents the character repeated that many times.
- If a character appears without a preceding number, it is repeated once.
Args:
s (str): The compressed string to be decompressed.
Returns:
str: The decompressed string, or -1 if the input string is empty.
"""
if len(s) == 0:
# Handle empty string case
return -1
number_chars = '0123456789' # Characters allowed in the number representation
i = 0 # Index pointing to the start of the current character sequence
j = 0 # Index iterating through the compressed string
output = [] # List to store decompressed characters
while j < len(s):
if s[j] in number_chars:
# Check if current character is a digit (part of the number)
j += 1
else:
# Extract the number representing the repetition
freq = int(s[i:j]) # Convert substring to integer
# Append the repeated character to the output list
output.append(freq * s[j])
# Move indices to the next character sequence
j += 1
i = j
return ''.join(output) # Join the list elements into a string
# Time Complexity: O(n) in average case, O(n^2) in worst case
# The loop iterates through the compressed string (s) with a maximum of n iterations (n being the length of the string).
# Inside the loop, most operations are constant time (character checks, converting substrings to integers).
# However, string concatenation in the worst case (highly repetitive patterns) can lead to quadratic time complexity.
# In the average case, string concatenation might not be a significant factor, resulting in linear time complexity.
# Space Complexity: O(n)
# The `output` list grows as characters are appended during decompression, potentially reaching a size of n (where n is the length of the input string).
# There's also additional space usage for temporary variables like `i` and `j`.
# However, these temporary variables have a constant space complexity and don't significantly affect the overall space complexity dominated by the `output` list.
# Notes on Approach and Reasoning:
# This code implements a function to uncompress a string based on a simple format.
# It iterates through the compressed string and identifies sequences of characters followed by numbers.
# If a character appears without a number, it's assumed to be repeated once.
# The code extracts the number (if present) and appends the corresponding character to a list the specified number of times.
# Finally, the list elements are joined into a string to form the decompressed output.
# This approach efficiently decodes the compressed string in a single pass. However, it's important to consider the potential worst-case time complexity due to string concatenation.