LeetCode 面试题 01.06. 字符串压缩（443. 压缩字符串）

面试题 01.06. 字符串压缩

? ?

字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。

示例1:

 输入："aabcccccaaa"
 输出："a2b1c5a3"

示例2:

 输入："abbccd"
 输出："abbccd"
 解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。

提示：

1. 字符串长度在[0, 50000]范围内。

思路：参考 LeetCode题解

根据题意，需要将「连续相同字符」压缩为「字符+出现次数」的格式。例如：aaa→a3,b→b1,aabbb→a2b3

双指针法：

• 分别定义下标 i = 0（慢指针），j = 1 （快指针）。
• 令?i?指向字符串的「首个字符」，?j?向前遍历，直到访问到「不同字符」时停止，此时 j?i?便是「首个字符」的连续出现次数，即可完成首个字符的压缩操作。
• 接下来，从下个字符开始，重复以上操作，直到遍历完成即可。
• 根据题目要求，最终返回「原字符串」和「压缩字符串」中长度较短的那个。

注意：在golang中，常规的字符串拼接方式，其性能较差，例如：“大量使用切片表达式” 和 “+?运算符”会频繁内存分配，最终导致性能较差。所以需要做性能优化，比如：使用byte数组，提前预估好容量大小，或者使用 strings.Builder。

string类型的 原理解析：

• 在底层，string类型的值会被存储在连续内存空间中（字节数组）。而大量使用切片表达式和“+”运算符会导致频繁内存分配。
• 因此，这些对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, 1
	for ; 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, 1
	for ; 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.Builder

	i, j := 0, 1
	for ; 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()
}