3163. 压缩字符串 III

题目描述

给你一个字符串 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⁵
word 仅由小写英文字母组成。

解法

方法一：双指针

思考

压缩规则是把连续相同字符写成次数（至多 \(9\)）加字符。手写下标容易在跨 \(9\) 时出错。

groupby 已按字符分段，每段长度再按 \(9\) 切开即可。

对每段 \(k\) 反复取 \(x=\min(9,k)\) 追加 str(x)+c。一遍线性拼接。

我们可以利用双指针，统计每个字符的连续出现次数。假如当前字符 \(c\) 连续出现了 \(k\) 次，然后我们将 \(k\) 划分成若干个 \(x\)，每个 \(x\) 最大为 \(9\)，然后将 \(x\) 和 \(c\) 拼接起来，将每个 \(x\) 和 \(c\) 拼接起来到结果中。

最后返回结果即可。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为字符串 word 的长度。

Python3JavaC++GoTypeScriptJavaScript

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('');
};

方法二：双指针

思考

方法一依赖分组库。双指针同样能在跨字符或满 \(9\) 时切段，且不引入额外中间列表。

维护段首 \(j\)，当 \(i\) 越界、字符变或长度到 \(9\) 时输出 \(i-j\) 与 \(word[j]\)，并令 \(j=i\)。

指针扫到 \(n\) 结束。与方法一同为线性，实现更贴近题面的「最多 \(9\) 个」。

TypeScriptJavaScript

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;
}

方法三：正则匹配

思考

双指针仍要手写切分条件。正则 (.)\1{0,8} 恰好匹配 \(1\) 到 \(9\) 个相同字符。

全局查找依次吞下最长不超过 \(9\) 的游程，长度为匹配串长。

每次把 len(m[0]) 与捕获的字符拼进答案。语义与前两法相同，代码更短。