comments | difficulty | edit_url | rating | source | tags | |
---|---|---|---|---|---|---|
true |
中等 |
1311 |
第 399 场周赛 Q2 |
|
给你一个字符串 word
,请你使用以下算法进行压缩:
- 从空字符串
comp
开始。当word
不为空 时,执行以下操作:<ul> <li>移除 <code>word</code> 的最长单字符前缀,该前缀由单一字符 <code>c</code> 重复多次组成,且该前缀长度 <strong>最多 </strong>为 9 。</li> <li>将前缀的长度和字符 <code>c</code> 追加到 <code>comp</code> 。</li> </ul> </li>
返回字符串 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 * 105
word
仅由小写英文字母组成。
我们可以利用双指针,统计每个字符的连续出现次数。假如当前字符
最后返回结果即可。
时间复杂度 word
的长度。
class Solution:
def compressedString(self, word: str) -> str:
g = groupby(word)
ans = []
for c, v in g:
k = len(list(v))
while k:
x = min(9, k)
ans.append(str(x) + c)
k -= x
return "".join(ans)
class Solution {
public String compressedString(String word) {
StringBuilder ans = new StringBuilder();
int n = word.length();
for (int i = 0; i < n;) {
int j = i + 1;
while (j < n && word.charAt(j) == word.charAt(i)) {
++j;
}
int k = j - i;
while (k > 0) {
int x = Math.min(9, k);
ans.append(x).append(word.charAt(i));
k -= x;
}
i = j;
}
return ans.toString();
}
}
class Solution {
public:
string compressedString(string word) {
string ans;
int n = word.length();
for (int i = 0; i < n;) {
int j = i + 1;
while (j < n && word[j] == word[i]) {
++j;
}
int k = j - i;
while (k > 0) {
int x = min(9, k);
ans.push_back('0' + x);
ans.push_back(word[i]);
k -= x;
}
i = j;
}
return ans;
}
};
func compressedString(word string) string {
ans := []byte{}
n := len(word)
for i := 0; i < n; {
j := i + 1
for j < n && word[j] == word[i] {
j++
}
k := j - i
for k > 0 {
x := min(9, k)
ans = append(ans, byte('0'+x))
ans = append(ans, word[i])
k -= x
}
i = j
}
return string(ans)
}
function compressedString(word: string): string {
const ans: string[] = [];
const n = word.length;
for (let i = 0; i < n; ) {
let j = i + 1;
while (j < n && word[j] === word[i]) {
++j;
}
let k = j - i;
while (k) {
const x = Math.min(k, 9);
ans.push(x + word[i]);
k -= x;
}
i = j;
}
return ans.join('');
}
/**
* @param {string} word
* @return {string}
*/
var compressedString = function (word) {
const ans = [];
const n = word.length;
for (let i = 0; i < n; ) {
let j = i + 1;
while (j < n && word[j] === word[i]) {
++j;
}
let k = j - i;
while (k) {
const x = Math.min(k, 9);
ans.push(x + word[i]);
k -= x;
}
i = j;
}
return ans.join('');
};
function compressedString(word: string): string {
let res = '';
for (let i = 1, j = 0; i <= word.length; i++) {
if (word[i] !== word[j] || i - j === 9) {
res += i - j + word[j];
j = i;
}
}
return res;
}
function compressedString(word) {
let res = '';
for (let i = 1, j = 0; i <= word.length; i++) {
if (word[i] !== word[j] || i - j === 9) {
res += i - j + word[j];
j = i;
}
}
return res;
}
function compressedString(word: string): string {
const regex = /(.)\1{0,8}/g;
let m: RegExpMatchArray | null = null;
let res = '';
while ((m = regex.exec(word))) {
res += m[0].length + m[1];
}
return res;
}
function compressedString(word) {
const regex = /(.)\1{0,8}/g;
let m = null;
let res = '';
while ((m = regex.exec(word))) {
res += m[0].length + m[1];
}
return res;
}