‘python实现字符串压缩,不使用python内部函数。利用字符重复出现的次数,编写一种方法,实现基本的字符串压缩功能。比如,字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短,则返回原先的字符串。你可以假设字符串中只包含大小写英文字母(a至z)。
时间: 2023-12-03 14:44:57 浏览: 95
可以使用双指针法来实现字符串压缩。具体实现步骤如下:
1. 定义两个指针,分别指向压缩后的字符串和原字符串的末尾。
2. 从原字符串的末尾开始向前遍历,记录当前字符出现的次数,并与前一个字符比较。若相同,则次数加1;若不同,则将前一个字符和次数写入压缩后的字符串。
3. 遍历完整个字符串后,将最后一个字符和次数写入压缩后的字符串。
4. 判断压缩后的字符串长度是否小于原字符串长度,如果是则返回压缩后的字符串,否则返回原字符串。
代码实现如下:
``` python
def compress_string(s):
n = len(s)
if n <= 1:
return s
compressed = ''
count = 1
i, j = n-1, n-2
while j >= 0:
if s[i] == s[j]:
count += 1
else:
compressed = s[j] + str(count) + compressed
count = 1
i -= 1
j -= 1
compressed = s[j+1] + str(count) + compressed
if len(compressed) < n:
return compressed
else:
return s
```
测试代码:
``` python
s1 = 'aabcccccaaa'
s2 = 'abcdefg'
print(compress_string(s1)) # a2b1c5a3
print(compress_string(s2)) # abcdefg
```
阅读全文