就地运行长度解码？

Question

给定一个行程编码的字符串,比如"A3B1C2D1E1",就地解码字符串.编码字符串的答案是"AAABCCDE".假设编码数组足够大以容纳解码的字符串,即您可以假设数组大小= MAX [length(encodedstirng),length(decodedstring)].

这似乎并不重要,因为仅将A3解码为"AAA"将导致原始字符串的'B'重写.

而且,不能假设解码的字符串总是大于编码的字符串.例如:编码字符串 - 'A1B1',解码字符串为'AB'.有什么想法吗？

并且它将始终是字母数字对,即您不会被要求转换0515为0000055555

Answer 1

如果我们还不知道,我们应首先扫描,将数字相加,以便计算解码字符串的长度.

它将始终是一个字母数字对,因此您可以1从字符串中删除s而不会产生任何混淆.

A3B1C2D1E1

变

A3BC2DE

下面是一些用C++编写的代码,用于1从字符串中删除s(O(n)复杂度).

// remove 1s
int i = 0; // read from here
int j = 0; // write to here
while(i < str.length) {
    assert(j <= i); // optional check
    if(str[i] != '1') {
        str[j] = str[i];
        ++ j;
    }
    ++ i;
}
str.resize(j); // to discard the extra space now that we've got our shorter string

现在,该字符串保证比最终解码的字符串短或相同.我们无法对原始字符串做出声明,但我们可以对此修改过的字符串进行说明.

(一个可选的,微不足道的步骤现在是2用前一个字母替换每一个.A3BCCDE但我们不需要这样做).

现在我们可以从最后开始工作了.我们已经计算了解码字符串的长度,因此我们确切知道最终字符的位置.我们可以简单地将字符串从短字符串的末尾复制到最终位置.

在从右到左的复制过程中,如果我们遇到一个数字,我们必须制作位于数字左侧的字母的多个副本.您可能担心这可能会覆盖过多的数据.但我们之前证明,我们的编码字符串或其任何子字符串永远不会长于其对应的解码字符串; 这意味着总会有足够的空间.