# [CareerCup] 1.5 Compress String 压缩字符串

1.5 Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2blc5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string.

Imagine you were concatenating a list of strings, as shown below. What would the running time of this code be? For simplicity, assume that the strings are all the same length (call this x) and that there are n strings.

public String joinWords(String[] words) {
String sentence = "";
for (String w : words) {
sentence = sentence + w;
}
return sentence;
}

On each concatenation, a new copy of the string is created, and the two strings are copied over, character by character. The first iteration requires us to copy x characters. The second iteration requires copying 2x characters.The third iteration requires 3x, and
so on.The total time therefore is 0(x + 2x + ... + nx). This reduces to 0(xn2). (Why isn't it 0(xnn)? Because 1 + 2 + ... + nequals n(n+l)/2,orO(n2).)

class Solution {
public:
string compress(string s) {
int newLen = countCompression(s);
if (newLen >= s.size()) return s;string res(newLen, ' ');
char c = s[0];
int cnt = 1, idx = 0;
for (int i = 1; i < s.size(); ++i) {
if (s[i] == c) ++cnt;
else {
res[idx++] = c;
for (auto a : to_string(cnt)) res[idx++] = a;
c = s[i];
cnt = 1;
}
}
res[idx++] = c;
for (auto a : to_string(cnt)) res[idx++] = a;
return res;
}
int countCompression(string s) {
if (s.empty()) return 0;
int res = 0, cnt = 1;
char c = s[0];
for (int i = 1; i < s.size(); ++i) {
if (s[i] == c) ++cnt;
else {
c = s[i];
res += 1 + to_string(cnt).size();
cnt = 1;
}
}
res += 1 + to_string(cnt).size();
return res;
}
};

|
19天前
|

【Java字符串操作秘籍】StringBuffer与StringBuilder的终极对决！
【8月更文挑战第25天】在Java中处理字符串时，经常需要修改字符串，但由于String对象的不可变性，频繁修改会导致内存浪费和性能下降。为此，Java提供了StringBuffer和StringBuilder两个类来操作可变字符串序列。StringBuffer是线程安全的，适用于多线程环境，但性能略低；StringBuilder非线程安全，但在单线程环境中性能更优。两者基本用法相似，通过append等方法构建和修改字符串。
43 1
|
25天前
|
NoSQL 安全 Java
Redis6入门到实战------ 三、常用五大数据类型（字符串 String）

25 2
|
9天前
|

C++(五)String 字符串类

8 0
|
12天前
|
C# 开发者 UED
WPF开发者必备秘籍：深度解析文件对话框使用技巧，打开与保存文件原来如此简单！
【8月更文挑战第31天】在WPF应用开发中，文件操作是常见需求。本文详细介绍了如何利用Microsoft.Win32命名空间下的OpenFileDialog和SaveFileDialog类来正确实现文件打开与保存功能。通过示例代码展示了如何设置文件过滤器、初始目录等属性，并使用对话框进行文件读写操作。正确使用文件对话框能显著提升用户体验，使应用更友好易用。
26 0
|
12天前
|
API C# 开发者
WPF图形绘制大师指南：GDI+与Direct2D完美融合，带你玩转高性能图形处理秘籍！
【8月更文挑战第31天】GDI+与Direct2D的结合为WPF图形绘制提供了强大的工具集。通过合理地使用这两种技术，开发者可以创造出性能优异且视觉效果丰富的WPF应用程序。在实际应用中，开发者应根据项目需求和技术背景，权衡利弊，选择最合适的技术方案。
29 0
|
19天前
|

【8月更文挑战第24天】Redis中的字符串类型作为其基石，不仅能够存储从简单文本到复杂格式如JSON的各种数据，还能通过多样化的命令实现包括但不限于自增自减、设置过期时间等高级功能，极大提升了其实用性和灵活性。例如，使用SET命令可添加或更新键值对，GET获取值，DEL删除键；同时，INCR和DECR支持对整数值的原子性增减操作，非常适合实现计数器等功能；通过EXPIRE命令设置过期时间，则适用于需要限时存储的应用场景。尽管名为“字符串”，但实际上还可存储图片、音频文件的Base64编码等形式的数据，为开发者提供了强大而灵活的工具。
27 0
|
21天前
|

【8月更文挑战第22天】
28 0
|
25天前
|

【揭秘】String vs StringBuilder vs StringBuffer：三大字符串类的秘密较量！你真的知道何时该用哪个吗？
【8月更文挑战第19天】探讨Java中String、StringBuilder与StringBuffer的区别及应用场景。String不可变，适合做哈希表键或多线程共享。StringBuilder支持动态修改字符串，适用于单线程环境以提高性能。StringBuffer与StringBuilder功能相似，但线程安全。示例代码展示各类型的基本用法。选择哪种类型取决于具体需求和性能考量。
27 0
|
2月前
|
Java 开发者 Python
Python中，字符串（String）是一种不可变的数据类型
Python中，字符串（String）是一种不可变的数据类型
33 5
|
2月前
|

Redis07命令-String类型字符串，不管是哪种格式，底层都是字节数组形式存储的，最大空间不超过512m，SET添加,MSET批量添加,INCRBY age 2可以，MSET,INCRSETEX
Redis07命令-String类型字符串，不管是哪种格式，底层都是字节数组形式存储的，最大空间不超过512m，SET添加,MSET批量添加,INCRBY age 2可以，MSET,INCRSETEX
53 0