3163. 压缩字符串 III

🟠   🔖  字符串  🔗 力扣 LeetCode

题目

Given a string word, compress it using the following algorithm:

• Begin with an empty string comp. While word is not empty, use the following operation:
• Remove a maximum length prefix of word made of a single character c repeating at most 9 times.
• Append the length of the prefix followed by c to comp.

Return the string comp.

Example 1:

Input: word = "abcde"

Output: "1a1b1c1d1e"

Explanation:

Initially, comp = "". Apply the operation 5 times, choosing "a", "b", "c", "d", and "e" as the prefix in each operation.

For each prefix, append "1" followed by the character to comp.

Example 2:

Input: word = "aaaaaaaaaaaaaabb"

Output: "9a5a2b"

Explanation:

Initially, comp = "". Apply the operation 3 times, choosing "aaaaaaaaa", "aaaaa", and "bb" as the prefix in each operation.

• For prefix "aaaaaaaaa", append "9" followed by "a" to comp.
• For prefix "aaaaa", append "5" followed by "a" to comp.
• For prefix "bb", append "2" followed by "b" to comp.

Constraints:

• 1 <= word.length <= 2 * 10^5
• word consists only of lowercase English letters.

题目大意

给你一个字符串 word，请你使用以下算法进行压缩：

• 从空字符串 comp 开始。当 word 不为空 时，执行以下操作：
• 移除 word 的最长单字符前缀，该前缀由单一字符 c 重复多次组成，且该前缀长度 最多 为 9 。
• 将前缀的长度和字符 c 追加到 comp 。

返回字符串 comp 。

示例 1：

输入： word = "abcde"

输出： "1a1b1c1d1e"

解释：

初始时，comp = "" 。进行 5 次操作，每次操作分别选择 "a"、"b"、"c"、"d" 和 "e" 作为前缀。

对每个前缀，将 "1" 和对应的字符追加到 comp。

示例 2：

输入： word = "aaaaaaaaaaaaaabb"

输出： "9a5a2b"

解释：

初始时，comp = ""。进行 3 次操作，每次操作分别选择 "aaaaaaaaa"、"aaaaa" 和 "bb" 作为前缀。

• 对于前缀 "aaaaaaaaa"，将 "9" 和 "a" 追加到 comp。
• 对于前缀 "aaaaa"，将 "5" 和 "a" 追加到 comp。
• 对于前缀 "bb"，将 "2" 和 "b" 追加到 comp。

提示：

• 1 <= word.length <= 2 * 10^5
• word 仅由小写英文字母组成。

解题思路

1. 初始化变量：

   • 创建一个空字符串 comp 用于存储压缩后的结果。
   • 使用一个索引 i 从 0 开始遍历 word。

2. 循环遍历字符串：

   • 在循环中，首先重置 count 为 0，用来计数当前字符的连续出现次数。
   • 使用 curChar 记录当前字符。

3. 计算前缀长度：

   • 使用一个嵌套的 while 循环，计算当前字符的最长前缀长度。条件是当前字符与 curChar 相等并且计数小于 9。
   • 每次匹配到相同字符时，增加计数并移动索引 i。

4. 构建压缩字符串：

   • 在外层循环中，将前缀长度和字符追加到 comp。

5. 返回结果：

   • 当字符串遍历完成后，返回最终的压缩结果 comp。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 word 的长度，每个字符最多被遍历一次。
• 空间复杂度：O(n)，在最坏情况下，压缩后的字符串可能与输入字符串相同（例如，所有字符都不同），因此需要额外的空间存储结果。

代码

/**
 * @param {string} word
 * @return {string}
 */
var compressedString = function (word) {
	let comp = '';
	let i = 0;

	while (i < word.length) {
		let count = 0;
		let curChar = word[i];

		// 计算当前字符的前缀长度（最多为9）
		while (i < word.length && word[i] === curChar && count < 9) {
			count++;
			i++;
		}

		// 将前缀的长度和字符追加到 comp
		comp += count + curChar;
	}

	return comp;
};

相关题目

题号	标题	题解	标签	难度	力扣
443	压缩字符串	[✓]	双指针 字符串	🟠	🀄️ 🔗
1531	压缩字符串 II		字符串 动态规划	🔴	🀄️ 🔗