2025-01-02：压缩字符串Ⅲ。用go语言，给定一个字符串 word，请按照以下算法进行压缩： 1.从一个空字符串 comp

2025-01-02：压缩字符串Ⅲ。用go语言，给定一个字符串 word，请按照以下算法进行压缩：

1.从一个空字符串 comp 开始。

2.当 word 仍有内容时，执行以下步骤：

2.1.找到 word 开头最长的由同一个字符 c 重复组成的前缀，且这个前缀的长度不能超过 9。

2.2.将前缀的长度和字符 c 追加到 comp 中。

3.最后返回压缩后的字符串 comp。

1 <= word.length <= 2 * 100000。

word 仅由小写英文字母组成。

输入：word = "abcde"。

输出："1a1b1c1d1e"。

解释：

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

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

答案2025-01-02：

chatgpt[1]

题目来自leetcode3163。

大体步骤如下：

1.初始化一个空的字符串 comp 用来存储压缩后的结果。

2.遍历输入的字符串 word。

3.每次循环中，找到以当前字符开始的最长重复子串，并记录其长度 k。

4.如果当前字符不等于下一个字符或者已经到达字符串末尾，则说明找到了一个重复子串，需进行处理。

5.如果 k <= 9，则直接将 k 和对应的字符 c 追加到 comp 中。

6.如果 k > 9，则将 k/9 个字符"c9"（表示9个重复的字符）和 k%9 个字符'ck'（表示余下的重复字符）追加到 comp 中。

7.更新当前重复子串的起始位置 i0 为当前位置 i。

8.将最终压缩后的字符串 comp 返回。

总的时间复杂度为 O(n)，其中 n 为输入字符串 word 的长度。这是因为代码中遍历了一遍输入字符串，并且每个字符只被访问了一次。

总的额外空间复杂度为 O(n)，主要由变量 t（用来存储压缩后的字符串）所占用的空间决定。

Go完整代码如下：

package main

import(

"fmt"

"bytes"

)

func compressedString(word string)string{

  t :=[]byte{}

  i0 :=-1

for i :=range word {

      c := word[i]

if i+1==len(word)|| c != word[i+1]{

          k := i - i0

          t =append(t, bytes.Repeat([]byte{'9', c}, k/9)...)

if k%9>0{

              t =append(t,'0'+byte(k%9), c)

}

          i0 = i

}

}

returnstring(t)

}

func main(){

  word :="abcde"

  result := compressedString(word)

  fmt.Println(result)

}

在这里插入图片描述Rust完整代码如下：

fn compressed_string(word:&str)->String{

letmut result=Vec::new();

letmut i0=-1;

letbytes= word.as_bytes();

letlen= bytes.len();

foriin0..len {

letc= bytes[i];

if i +1== len || c != bytes[i +1]{

letk=(i asisize)- i0;

// 处理连续字符的数量

          result.extend(std::iter::repeat(9).take((k /9)asusize).map(|_|9).map(|n| n asu8+ c));

if k %9>0{

              result.push('0'asu8+(k %9)asu8);

              result.push(c);

}

          i0 = i asisize;

}

}

String::from_utf8(result).unwrap()

}

fnmain(){

letword="abcde";

letresult=compressed_string(word);

println!("{}", result);

}

在这里插入图片描述引用链接