根據給定的編碼技術，從結果字串重建原始字串

---

在這個問題中，我們需要根據給定的字串構建原始字串。給定的字串是使用給定的規則從原始字串生成的。

在這裡，我們可以使用給定的加密規則和加密字串，透過反向應用加密規則來找到解密字串。

問題陳述 – 我們給定一個長度為 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。之後，我們確保字串遵循第一和第二個條件。因此，如果我們反向遵循加密規則，則可以解密字串。