遞迴解碼以計數後跟子字串編碼的字串


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

我們可以採用三種不同的方法來解決這個問題,我們可以使用兩個棧或一個棧來解決這個問題。此外,我們也可以不用兩個棧來解決這個問題。

問題陳述 - 我們得到一個包含開閉括號、字母和數字字元的字串 str。我們需要遞迴地解碼該字串。

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

  • <count>[chars] - ‘chars’ 應該在結果字串中出現 count 次。

示例

輸入

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

輸出

ddcnncnncnn

解釋

  • 首先,我們解碼 2[n],得到 "2[d]3[cnn]"。

  • 接下來,我們解碼 3[cnn]。所以,我們得到“2[d]cnncnncnn”。

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

輸入

5[i]

輸出

iiiii

解釋 - 解碼給定字串後,我們得到 5 個 'I'。

輸入

3[fg]

輸出

fgfgfg

解釋 - 解碼輸入字串後,我們得到 3 個 'fg'。

方法 1

在這種方法中,我們將使用兩個棧來解決問題。當我們得到左括號時,我們將它壓入棧中。同樣,當我們得到數字字元時,我們將所有數字字元附加起來以構成一個有效的正整數,並將它們新增到整數棧中。之後,當我們得到右括號時,我們將從棧中彈出整數和字元。

演算法

步驟 1 - 定義 ‘instSt’ 棧來儲存數字,‘strSt’ 來儲存字串字元和左括號。此外,初始化 ‘answer’ 來儲存結果字串,‘tempStr’ 來儲存臨時字串。

步驟 2 - 開始遍歷字串。

步驟 3 - 將 ‘num’ 初始化為 0,以儲存當前字元為數字時的數字。

步驟 3.1 - 如果第 p 個索引處的字元是數字,則遍歷字串,直到我們得到字母字元或括號。在迴圈中,將 ‘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 - 接下來,我們需要將 ‘temp_Str’ 附加到 ‘answer’ 字串中 ‘num’ 次。

步驟 4.5 - 將 ‘answer’ 字串的每個字元插入 ‘strSt’ 棧中,並將其重新初始化為空字串。

步驟 5 - 如果當前字元是左括號,請按照以下步驟操作。

步驟 5.1 - 如果前一個字元是數字,則將 ‘[‘ 推入棧 ‘StrSt’。否則,將 ‘[‘ 推入 StrSt 棧,將 1 推入 ‘instSt’ 棧。

步驟 6 - 如果我們得到字母字元,則將其推入 ‘strSt’ 棧。

步驟 7 - 最後,使用迴圈從 ‘strSt’ 棧中刪除所有字元,附加到 ‘answer’ 字串中,並返回它。

示例

#include <bits/stdc++.h>
using namespace std;

string decodeTheString(string alpha) {
    stack<int> instSt;
    stack<char> 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 - 如果 ‘answer’ 字串在頂部包含數字,則使用數字建立一個整數,並將其儲存在 number 變數中。

步驟 8 - 反轉數字字串。

步驟 9 - 使用 stoi() 方法將字串轉換為數字。

步驟 10 - 將 temp_Str 字串附加到 answer 字串 ‘number’ 次。

步驟 11 - 返回 ‘answer’ 字串。

示例

#include <bits/stdc++.h>
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),用於儲存數字和臨時字串。

更新於:2023年8月14日

瀏覽量 232

啟動您的職業生涯

透過完成課程獲得認證

開始
廣告