字符串解压 : Reduce time and space complexity

Question

N 轮 压缩在字符串上运行，其中每一轮用一个特殊字符(使用字典)替换一些字符模式。

给定这个压缩字符串和用于压缩的字典，我们需要找到原始字符串。

例如:

用于压缩的字典:

b12k -> ?

a?l -> #

#mn -> !

因此，字符串 ab12klmn 被压缩为 !

哪种数据结构最适合存储此字典，以便解压缩是 O(n) 操作，使用的额外空间最少？

我尝试过的:这是一个面试问题，我将字典存储在一个映射中，目标字母表(压缩字典的)作为我的映射的键，并将解压缩的字符串作为值。然后遍历给定的字符串，用它们各自的扩展替换特殊字符。例如:

! -> ab12klmn

# -> ab12k

? -> b12k

然后为了减少字符串模式的重复，我对这本字典做了树状结构，但面试官并不满意。我可以在哪里改进此解决方案？

Answer 1

我知道我们需要从给定的压缩字符串中取回原始字符串。

您可以在此处使用的最佳数据结构可以是二维向量(动态数组)。我将尝试解释为什么这是解决此问题的最佳数据结构。

1. 当我们使用映射时，我们在寻找特定键时引入了一个logn 因子。使用向量，如果您知道搜索查询的位置，则可以在 O(1) 中完成。
2. 当我们使用向量时，我们不会浪费任何额外的内存块。 map 也是如此。但是，如果您使用二维数组，则会浪费不必要的内存。

但由于只有 256 个字符，我们将按如下方式存储字典。让我们有一个最多 256 行的二维字符串向量。对于这个例子

b12k -> ?

a?l -> #

#mn -> !

所以我们将把“b12k”存储在 v[63] 作为 '?' 的 ASCII 值是 63。类似地，我们将存储我们将在 v[35] 存储“a?l”，因为 '#' 的 ASCII 值是 35 等等，

现在如何找到原始字符串:

我们从压缩字符串开始。

1. 初始化将存储最终答案的字符串。我们称它为 origString = ""。

2. 开始遍历字符串。如果它是非特殊字符，则将此字符添加到 origString。

3. 如果我们发现任何特殊字符，只需转到该字符的 ASCII 值及其在二维向量中的相应位置。

4. 转到第 2 步。

伪代码是

    origString = "";
    func getOriginalFromCompressed(string s) 
        for i = [0:s.length()-1]
            if(v[s[i]].length()) getOriginalFromCompressed(v[s[i]]);
            else                 origString = stringConcat(origString,s[i]);   //add the charcacter to your final ans
        end for
    end func    

origString 具有原始字符串。

所以这个解的时间和空间复杂度是O(n)。其中 n = 给定字典中所有字符串的长度总和。