根据给定的编码技术，从结果字符串重建原始字符串

---

在这个问题中，我们需要根据给定的字符串构建原始字符串。给定的字符串是使用给定的规则从原始字符串生成的。

在这里，我们可以使用给定的加密规则和加密字符串，通过反向应用加密规则来找到解密字符串。

问题陈述 – 我们给定一个长度为 N 的二进制字符串 bin_str 和一个正整数 k。二进制字符串是通过遵循以下操作并使用 x 值从“enc”字符串构建的。

• 如果 enc_i-k 等于 1，则 bin_str_i 等于 1。

• 如果 enc_i+k 等于 1，则 bin_str_i 等于 1。

• 如果以上两个条件都为假，则 bin_str_i 为 0。

示例

输入

bin_Str = "11001", k = 2

输出

00110

解释 – 让我们了解如何从输出字符串获取 bin_str 字符串的每个字符。

• bin_Str[0] = ‘1’ – 在输出字符串中，索引为 (0 + k) 的字符为 ‘1’。

• bin_Str[1] = ‘1’ – 在输出字符串中，索引为 (1 + k) 的字符为 ‘1’。

• bin_Str[2] = ‘0’ – 在输出字符串中，索引为 (2 + k) 和 (2 – k) 的字符为 0。

• bin_Str[3] = ‘0’ - 在输出字符串中，索引为 (3 + k) 的字符不存在，并且 (3 – k) 为 0。

• bin_Str[4] = ‘1’ - 在输出字符串中，索引为 (4 - k) 的字符为 ‘1’。

我们选择输出字符串，因为我们根据给定的加密规则从它构建 bin_Str 字符串。

输入

bin_Str = "00011", k = 2

输出

-1

解释 – 原始字符串不存在。

方法 1

在这种方法中，我们将创建一个包含所有 1 的字符串。之后，我们将根据给定的加密规则修改字符串，最后我们将交叉检查我们是否可以获得原始字符串。

算法

步骤 1 – 使用等于“bin_str”字符串长度的“1”总数初始化“enc”字符串。

步骤 2 – 开始遍历字符串，如果第 p 个索引处的字符为“0”，则表示如果存在，则 (p – k) 或 (p + k) 字符应为 0。因此，如果存在，则将 enc[p-k] 和 enc[p+k] 更新为“0”。

步骤 3 – 在“enc”字符串中，如果第 p 个索引处的字符为“1”，则执行以下步骤。

步骤 3.1 – 如果 p – k 存在，enc[p – k] 等于 1，或者 p + k 存在且 enc[p + k] 等于 1，则继续进行下一次迭代。

步骤 3.2 – 否则，返回“-1”，因为字符串不存在。

步骤 4 – 最后返回“enc”字符串。

示例

#include <iostream>
using namespace std;

string generateString(string bin_Str, int K) {
    // Get string size
    int len = bin_Str.size();
    // Initialize the string with all 1's
    string enc(len, '1');
    // Traverse string to update
    for (int p = 0; p < len; ++p) {
        // For the character '0'
        if (bin_Str[p] == '0') {
            // If p-k or p + k exists, set it to '0' according to the reverse of the encryption condition
            if (p - K >= 0) {
                enc[p - K] = '0';
            } 
            if (p + K < len) {
                enc[p + K] = '0';
            }
        }
    }
    // Cross check resultant string
    for (int p = 0; p < len; ++p) {
        // For character '1'
        if (bin_Str[p] == '1') {
            // If p - k and p + k is valid and is equal to '1', continue.
            if ((p - K >= 0 && enc[p - K] == '1') || (p + K < len && enc[p + K] == '1')) {
                continue;
            } else {
                return "-1";
                break;
            }
        }
    }
    return enc;
}
int main() {
    // Given input
    string bin_Str = "11001";
    int K = 2;
    string result = generateString(bin_Str, K);
    if (result == "-1") {
        cout << "The required string is not exist!";
    } else {
        cout << "The original string is: " << result << endl;
    }

    return 0;
}

输出

The original string is: 00110

时间复杂度 – O(N) 以迭代字符串。

空间复杂度 – 用于辅助字符串的 O(N)。

在问题解决方案中，我们使用了加密规则从加密字符串中获取原始字符串。我们首先按照第一个条件将 1 更改为 0。之后，我们确保字符串遵循第一和第二个条件。因此，如果我们反向遵循加密规则，则可以解密字符串。