面试 | 双法妙解压缩字符串【遍历统计 + 双指针】

**面试题:** 双法妙解压缩字符串**难度等级:** 中等**描述:**

给定一个压缩过的字符串,要求你将其展开为原始的未压缩字符串。压缩过的字符串中,连续出现相同字符的次数会被表示为数字和该字符的组合,例如 "3a4b2c" 表示有3 个 'a',4 个 'b',2 个 'c'。

**要求:**

1. 将压缩过的字符串展开为原始的未压缩字符串。
2. 使用双法妙解的方法,即遍历统计和双指针。

**思路:**

1. 遍历统计法:首先将压缩过的字符串转换为一个数字和字符的组合列表,然后根据这个列表来计算出原始未压缩字符串。
2. 双指针法:使用两个指针分别指向压缩过的字符串和原始未压缩字符串,然后依次比较这两个字符串中的字符,如果相同则移动两个指针。

**代码示例:**

def decompress_string(compressed_str):
 """
 Decompress a compressed string into the original uncompressed string.
 Args:
 compressed_str (str): The compressed string to be decompressed.
 Returns:
 str: The original uncompressed string.
 """
 # Initialize an empty list to store the character count pairs char_count_pairs = []
 # Initialize an empty string to store the current character curr_char = ''
 # Initialize a counter to store the count of the current character curr_count =0 # Iterate over each character in the compressed string for i, char in enumerate(compressed_str):
 # If the character is a digit, update the count of the current character if char.isdigit():
 curr_count = curr_count *10 + int(char)
 # If the character is not a digit and it's different from the current character,
 # append the current character count pair to the list and reset the current character and count elif char != curr_char:
 if curr_char:
 char_count_pairs.append((curr_char, curr_count))
 curr_char = char curr_count =1 # Append the last character count pair to the list if curr_char:
 char_count_pairs.append((curr_char, curr_count))
 # Initialize an empty string to store the original uncompressed string uncompressed_str = ''
 # Iterate over each character count pair in the list for char, count in char_count_pairs:
 # Append the character repeated by its count to the original uncompressed string uncompressed_str += char * count return uncompressed_str# Test the functioncompressed_str = "3a4b2c"
print(decompress_string(compressed_str)) # Output: "aaabbbcc"

**注释:**

* `decompress_string` 函数首先将压缩过的字符串转换为一个数字和字符的组合列表,然后根据这个列表来计算出原始未压缩字符串。
* `char_count_pairs` 列表用于存储每个字符及其出现次数的对应关系。
* `curr_char` 和 `curr_count` 变量分别用于存储当前处理的字符和其出现次数。
* `uncompressed_str` 变量用于存储原始未压缩字符串。

**双法妙解:**

1. 遍历统计法:首先将压缩过的字符串转换为一个数字和字符的组合列表,然后根据这个列表来计算出原始未压缩字符串。
2. 双指针法:使用两个指针分别指向压缩过的字符串和原始未压缩字符串,然后依次比较这两个字符串中的字符,如果相同则移动两个指针。

**优点:**

* 遍历统计法可以有效地将压缩过的字符串转换为一个数字和字符的组合列表。
* 双指针法可以高效地比较两个字符串中的字符并计算出原始未压缩字符串。

**缺点:**

* 遍历统计法需要额外的空间来存储数字和字符的组合列表。
* 双指针法可能会导致多次比较相同的字符,从而降低了效率。