本文主要是介绍LeetCode 面试题 01.06. 字符串压缩（443. 压缩字符串），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
对于算法题，按题型类别刷题才会更有成效，因此我这里在网上搜索并参考了下 “🔥 LeetCode 热题 HOT 100” 的题型归类，并在其基础上做了一定的完善，希望能够记录自己的刷题历程，有所收获！点击下发链接跳转~⬇️⬇️⬇️
🔥 LeetCode 热题 HOT 100【题型归类汇总，助力刷题】
面试题 01.06. 字符串压缩
字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串
aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。示例1:
输入："aabcccccaaa" 输出："a2b1c5a3"示例2:
输入："abbccd" 输出："abbccd" 解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。提示：
- 字符串长度在[0, 50000]范围内。
思路：参考 LeetCode题解
根据题意，需要将「连续相同字符」压缩为「字符+出现次数」的格式。例如：aaa→a3,b→b1,aabbb→a2b3
双指针法：
- 分别定义下标 i = 0（慢指针），j = 1 （快指针）。
- 令 i 指向字符串的「首个字符」， j 向前遍历，直到访问到「不同字符」时停止，此时 j−i 便是「首个字符」的连续出现次数，即可完成首个字符的压缩操作。
- 接下来，从下个字符开始，重复以上操作，直到遍历完成即可。
- 根据题目要求，最终返回「原字符串」和「压缩字符串」中长度较短的那个。
注意：
在golang中，常规的字符串拼接方式，其性能较差，例如：“大量使用切片表达式” 和 “+ 运算符”会频繁内存分配，最终导致性能较差。
所以 在 golang 中，有大量字符串拼接的场景下，不建议直接使用 “+” 运算符来拼接字符串，以避免频繁的内存分配问题。
我们在以上思路的基础上做性能优化：
- 使用byte数组：提前预估好容量大小，例如 方法2
- 使用 strings.Builder：例如 方法3
string类型的 原理解析：
- 在底层，string类型的值会被存储在连续内存空间中（byte类型的字节数组）。而大量使用切片表达式和“+”运算符会导致频繁内存分配。
- 因此，这些对string的操作相当于对底层字节数组进行操作，会导致更多的内存重分配开销，影响性能。
时间复杂度：O(N)
其中 N 为输入字符串 S 长度。指针 i , j 皆完成一次字符串遍历，循环 N+N=2N 次，使用 O(N) 线性时间。
空间复杂度：O(N)
res 用于临时存储压缩结果。最差情况下（当原字符串的所有相邻字符都不同时，a→a1 一个变两个），压缩字符串的长度为 2N，占用 O(2N)=O(N) 大小的额外空间。
// 版本1 字符串拼接（性能不佳）
// 在底层，string的值会被存储在连续内存空间中（字节数组）。
// 大量使用切片表达式和“+”运算符会导致频繁内存分配。
// 因此，这些对string的操作相当于对底层字节数组进行操作，会导致更多的内存重分配开销，影响性能。
func compressString(S string) string {sLen := len(S)if sLen <= 1 {return S}res := ""i, j := 0, 1for ; j < sLen; j++ {if S[i] != S[j] {res += string(S[i]) + strconv.Itoa(j-i)i = j}if len(res) >= sLen {return S}}// 在for循环中，S末尾的结果集还未处理，这里需要追加上来res += string(S[i]) + strconv.Itoa(j-i)// 若“压缩”后的字符串没有变短，则返回原先的字符串if len(res) >= sLen {return S}return res
}// 版本2：使用byte数组优化
func compressString(S string) string {sLen := len(S)if sLen <= 1 {return S}// 数组提前预估容量，避免重分配res := make([]byte, 0, sLen)i, j := 0, 1for ; j < sLen; j++ {if S[i] != S[j] {res = append(res, S[i])res = append(res, []byte(strconv.Itoa(j-i))...)// 这两个append的操作要分开写，不支持合并一起写；后面同理// res = append(res, S[i], byte(strconv.Itoa(j-i))) // 错误i = j}if len(res) >= sLen {return S}}res = append(res, S[i])res = append(res, []byte(strconv.Itoa(j-i))...)// 若“压缩”后的字符串没有变短，则返回原先的字符串if len(res) >= sLen {return S}return string(res)
}// 版本3：使用go strings.Builder优化
func compressString(S string) string {sLen := len(S)if sLen <= 1 {return S}// res := ""var sb strings.Builderi, j := 0, 1for ; j < sLen; j++ {if S[i] != S[j] {sb.WriteByte(S[i])sb.WriteString(strconv.Itoa(j - i))// res += string(S[i]) + strconv.Itoa(j-i)i = j}}sb.WriteByte(S[i])sb.WriteString(strconv.Itoa(j - i))// res += string(S[i]) + strconv.Itoa(j-i)if sb.Len() >= sLen {return S}return sb.String()
}这篇关于LeetCode 面试题 01.06. 字符串压缩（443. 压缩字符串）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
