3163. 压缩字符串 III
3163. 压缩字符串 III
题目
Given a string word
, compress it using the following algorithm:
- Begin with an empty string
comp
. Whileword
is not empty, use the following operation: - Remove a maximum length prefix of
word
made of a single characterc
repeating at most 9 times. - Append the length of the prefix followed by
c
tocomp
.
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"
tocomp
. - For prefix
"aaaaa"
, append"5"
followed by"a"
tocomp
. - For prefix
"bb"
, append"2"
followed by"b"
tocomp
.
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
仅由小写英文字母组成。
解题思路
初始化变量:
- 创建一个空字符串
comp
用于存储压缩后的结果。 - 使用一个索引
i
从0
开始遍历word
。
- 创建一个空字符串
循环遍历字符串:
- 在循环中,首先重置
count
为0
,用来计数当前字符的连续出现次数。 - 使用
curChar
记录当前字符。
- 在循环中,首先重置
计算前缀长度:
- 使用一个嵌套的
while
循环,计算当前字符的最长前缀长度。条件是当前字符与curChar
相等并且计数小于9
。 - 每次匹配到相同字符时,增加计数并移动索引
i
。
- 使用一个嵌套的
构建压缩字符串:
- 在外层循环中,将前缀长度和字符追加到
comp
。
- 在外层循环中,将前缀长度和字符追加到
返回结果:
- 当字符串遍历完成后,返回最终的压缩结果
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 | 字符串 动态规划 |