实现一个算法来压缩一个字符串。压缩的要求如下: 需要判断压缩能不能节省空间,仅在压缩后字符串比原字符串长度更短时进行压缩。 压缩的格式是将连续相同字符替换为字符 + 数字形式,例如 "AAABCCDDDD" 变为 "A3BC2D4"。
时间: 2024-10-26 19:16:15 浏览: 43
C语言中压缩字符串的简单算法小结
要实现一个这样的字符串压缩算法,你可以采用类似滑动窗口的方式来操作。以下是步骤和伪代码描述:
1. 初始化两个指针,`start` 和 `end`,都指向字符串的第一个字符,分别表示当前连续字符的起始位置和结束位置。同时设置一个变量 `count` 用于记录字符的计数,初始值为1。
2. 当 `end < string.length` 时,循环执行以下操作:
a. 比较 `string[end]` 是否与 `string[end - count + 1]` 相同,如果相同则 `count++`;如果不相同,则更新结果字符串(添加当前字符及其计数),并把 `start` 移到 `end - count + 1`,然后 `count = 1`。
b. `end++`。
3. 循环结束后,检查最后一个字符是否需要添加计数。如果不是最后一位,还需要处理一下,添加该字符后的计数值。
4. 更新结果字符串,将原始字符替换为字符+数字形式(如“A3”、“BC2”等)。如果新的结果字符串长度小于原始字符串长度,说明进行了压缩,返回压缩后的字符串;否则,保持原样,因为压缩没有节省空间。
```python
def compress_string(s):
if len(s) <= 1:
return s
result = ''
start = end = 0
count = 1
while end < len(s):
if end + 1 < len(s) and s[end] == s[end + 1]:
count += 1
end += 1
else:
result += s[start] + str(count)
start = end
count = 1
# 处理最后一个字符
if end != len(s):
result += s[start:end + 1]
compressed_len = len(result)
original_len = len(s)
# 如果压缩后变短了,返回压缩后的字符串;否则保持原样
if compressed_len < original_len:
return result
else:
return s
# 示例
original = "AAABCCDDDD"
compressed = compress_string(original)
print(f"Original: {original}, Compressed: {compressed}")
```
阅读全文