遞歸解碼一個以計數後跟子字串編碼的字串

在這個問題中，我們需要透過重複新增總計數次數來解碼給定的字串。

我們可以採用三種不同的方法來解決問題，並且可以使用兩個堆疊或一個堆疊來解決問題。另外，我們可以在不使用兩個堆疊的情況下解決問題。

問題陳述 - 我們給了一個字串 str ，其中包含左括號和右括號、字母和數字字元。我們需要遞歸地解碼字串。

以下是解碼字串的模式或規則。

• [chars] - “chars”應該在結果字串中出現 count 次。

範例

輸入

str = "2[d]3[c2[n]]";

輸出

ddcnncnncnn

說明

• 首先，我們解碼 2[n]，得到「2[d]3[cnn]」。

• 接下來，我們解碼 3[cnn]。所以，我們得到「2[d]cnnncnncnn」。

• 接下來，我們解碼 2[d]。所以，我們得到“ddcnnncnncnn”。

輸入

5[i]

輸出

iiiii

解釋- 當我們解碼給定的字串時，我們得到 5 個「I」。

輸入

3[fg]

輸出

fgfgfg

解釋- 當我們解碼輸入字串時，我們得到「fg」3次。

方法 1

我們將使用兩個堆疊來解決此方法中的問題。當我們得到一個左括號時，我們將其推入堆疊。此外，當我們獲取數字字元時，我們將所有數字字元附加到有效的正整數並將它們添加到整數堆疊中。之後，當我們得到右括號時，我們從堆疊中彈出整數和字元。

演算法

第 1 步- 定義「instSt」堆疊來儲存數字，定義「strSt」來儲存字串字元和左括號。此外，初始化“answer”以儲存結果字串，初始化“tempStr”以儲存臨時字串。

第 2 步- 開始遍歷字串。

第 3 步- 如果目前字元是數字，則用 0 初始化「num」以儲存數字。

步驟 3.1 − 如果第 p^th 索引處的字元是數字，則遍歷字串，直到得到字母字元或括號。在循環中，將“num”的先前值乘以 10，並將當前數字加到其中。

步驟 3.2− 將「p」的值增加 1。

步驟 3.3 - 將數字值推送到「instSt」堆疊。

步驟 4 - 如果第 p 個索引處的字元是右括號，請依照下列步驟操作。

步驟 4.1- 用空字串初始化「temp_str」。之後，如果‘instSt’不為空，則從堆疊中彈出頂部整數。

步驟 4.2 - 現在，使用循環，直到我們得到左括號或堆疊從「strSt」堆疊變空。另外，將字元附加到“temp_str”。

步驟 4.3 - 如果我們因為「[」而停止對角色進行大便，請將其刪除。

步驟 4.4 - 接下來，我們需要在「answer」字串中附加「temp_Str」「num」次。

步驟 4.5 - 將「answer」字串的每個字元插入「strSt」堆疊中，並使用空字串重新初始化它。

步驟 5 − 如果目前字元是左括號，請依照下列步驟操作。

步驟 5.1 − 如果前一個字元是數字，則將「[」推入堆疊「StrSt」。否則，將「[」壓入 StrSt 堆疊，並將 1 壓入「instSt」堆疊。

第 6 步− 如果我們得到一個字母字符，則將其推入「strSt」堆疊。

第 7 步- 最後，使用循環從「strSt」堆疊中刪除所有字符，附加到「answer」字串，然後返回它。

範例

#include 
using namespace std;

string decodeTheString(string alpha) {
    stack instSt;
    stack StrSt;
    string tempStr = "", answer = "";
    // Iterate the string
    for (int p = 0; p < alpha.length(); p++) {
        int num = 0;
        // If we find the number, extract the number and push it to the stack
        if (alpha[p] >= '0' && alpha[p] <= '9') {
            // Making iterations until we get an alphabetic character
            while (alpha[p] >= '0' && alpha[p] <= '9') {
                num = num * 10 + alpha[p] - '0';
                p++;
            }
            p--;
            instSt.push(num);
        }
        // If the character at the pth index is closing bracket
        else if (alpha[p] == ']') {
            tempStr = "";
            num = 0;
            // Pop the number from the stack
            if (!instSt.empty()) {
                num = instSt.top();
                instSt.pop();
            }
            // Pop the character until we get the opening bracket
            while (!StrSt.empty() && StrSt.top() != '[') {
                tempStr = StrSt.top() + tempStr;
                StrSt.pop();
            }
            // remove the opening bracket
            if (!StrSt.empty() && StrSt.top() == '[')
                StrSt.pop();
            // Append string to answer for num times
            for (int j = 0; j < num; j++)
                answer = answer + tempStr;
            // Insert the updated string again into the stack
            for (int j = 0; j < answer.length(); j++)
                StrSt.push(answer[j]);
            answer = "";
        }
        // If the character at the pth index is an opening bracket
        else if (alpha[p] == '[') {
            if (alpha[p - 1] >= '0' && alpha[p - 1] <= '9') {
                StrSt.push(alpha[p]);
            } else {
                StrSt.push(alpha[p]);
                instSt.push(1);
            }
        } else {
            // Push alphabetic character in the string stack.
            StrSt.push(alpha[p]);
        }
    }
    // Pop all the elements, make a string, and return.
    while (!StrSt.empty()) {
        answer = StrSt.top() + answer;
        StrSt.pop();
    }
    return answer;
}
// starting code
int main() {
    string str = "2[d]3[c2[n]]";
    cout << "The resultant string after decoding it is - " << decodeTheString(str) << endl;
    return 0;
}

輸出

The resultant string after decoding it is - ddcnncnncnn

時間複雜度− O(n^2)，因為我們遍歷字串並不斷向堆疊推送和彈出元素。

空間複雜度− 在堆疊中儲存元素的 O(n)。

方法2

我們將在這種方法中不使用堆疊來解決問題。另外，我們將使用reverse()方法來反轉字串。

演算法

第 1 步- 開始迭代字串。

第 2 步− 如果第 i 個字元是“]”，則將其推入“answer”字串。否則，請按照以下步驟操作。

第 3 步- 使用空字串初始化「temp_Str」。

第 4 步- 繼續遍歷「answer」字串，直到該字串為空或找到「[」字元。另外，繼續從“answer”字串中彈出最後一個字元並將其附加到“temp_Str”字串中。

第 5 步- 當我們從找到「]」括號的位置向後遍歷時，反轉「temp_Str」字串。

第 6 步- 從「answer」字串中刪除最後一個字元以刪除「[」字元。

第 7 步- 如果“答案”字符串顶部包含数字，则使用数字生成一个整数，并将其存储在 number 变量中。

第 8 步- 反转数字字符串。

第 9 步- 使用 stoi() 方法将字符串转换为数字。

步骤 10 - 将 temp_Str 字符串附加到答案字符串“number”次。

第 11 步- 返回“答案”字符串。

示例

#include 
using namespace std;

string decodeTheString(string alpha) {
    string answer = "";
    // iterate the string characters
    for (int i = 0; i < alpha.length(); i++) {
        // for all other characters except the closing bracket
        if (alpha[i] != ']') {
            answer.push_back(alpha[i]);
        } else {
            // Extract the substring lying within the pair
            string temp_str = "";
            // Keep on popping characters until '[' is found.
            while (!answer.empty() && answer.back() != '[') {
                temp_str.push_back(answer.back());
                answer.pop_back();
            }
            // get original string by reversing the string
            reverse(temp_str.begin(), temp_str.end());
            // open bracket removal
            answer.pop_back();
            // get integer value before the '[' character
            string number = "";
            // get the number before opening bracket
            while (!answer.empty() && answer.back() >= '0' && answer.back() <= '9') {
                number.push_back(answer.back());
                answer.pop_back();
            }
            // reverse number string
            reverse(number.begin(), number.end());
            // convert string to integer
            int numInt = stoi(number);
            for (int p = 0; p < numInt; p++) {
                answer += temp_str;
            }
        }
    }
    return answer;
}
int main() {
    string str = "2[d]3[c2[n]]";
    cout << "The resultant string after decoding it is - " << decodeTheString(str) << endl;
    return 0;
}

输出

The resultant string after decoding it is − ddcnncnncnn

时间复杂度− O(N^2)，因为我们遍历字符串并在循环内使用reverse()方法。

空间复杂度− O(N) 来存储数字和临时字符串。

以上是遞歸解碼一個以計數後跟子字串編碼的字串的詳細內容。更多資訊請關注PHP中文網其他相關文章！