时间戳

首页 > 解决方案 > 字符串解压：降低时间和空间复杂度

string - 字符串解压：降低时间和空间复杂度

问题描述

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

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

例如：

用于压缩的字典：

b12k -> ?

a?l -> #

#mn -> ！

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

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

我试过的： 这是一个面试问题，我将字典存储在一个地图中，目标字母（压缩字典的）作为我的地图的键，解压缩的字符串作为值。然后遍历给定的字符串，用它们各自的扩展替换特殊字符。例如：

！-> ab12klmn

# -> ab12k

? -> b12k

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

标签： stringalgorithmdata-structurescompression

解决方案

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

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

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

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

b12k -> ?

a?l -> #

#mn -> ！

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

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

我们从压缩字符串开始。

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

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

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

  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 =给定字典中所有字符串的长度总和。

推荐阅读