跳至主要內容

3163. 压缩字符串 III


3163. 压缩字符串 IIIopen in new window

🟠   🔖  字符串  🔗 力扣open in new window LeetCodeopen in new window

题目

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 用于存储压缩后的结果。
    • 使用一个索引 i0 开始遍历 word
  2. 循环遍历字符串

    • 在循环中,首先重置 count0,用来计数当前字符的连续出现次数。
    • 使用 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压缩字符串open in new window[✓]双指针 字符串
1531压缩字符串 IIopen in new window字符串 动态规划