カウントとそれに続く部分文字列としてエンコードされた文字列を再帰的にデコードします

この問題では、合計カウント回数を繰り返し加算することで、指定された文字列をデコードする必要があります。

問題には 3 つの異なる方法でアプローチでき、問題を解決するために 2 つのスタックまたは 1 つのスタックを使用できます。また、スタックを 2 つ使用せずに問題を解決することもできます。

問題文 - 左括弧、右括弧、英字、数字を含む文字列 str が与えられています。文字列を再帰的にデコードする必要があります。

以下は、文字列をデコードするためのパターンまたはルールです。

• [chars] - 「chars」は結果文字列に count 回出現する必要があります。

＃＃＃例＃＃＃ ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー

イラスト

まず、2[n] をデコードして、「2[d]3[cnn]」を取得します。

次に、3[cnn]をデコードします。したがって、「2[d]cnnncnncnn」が得られます。

次に、2[d]をデコードします。したがって、「ddcnnnncnncnn」が得られます。

• ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー
• 説明

  - 指定された文字列をデコードすると、5 つの「I」が得られます。

  ＃＃＃＃＃＃入力＃＃＃＃＃＃ リーリー ＃＃＃＃＃＃出力＃＃＃＃＃＃ リーリー
• 説明

  - 入力文字列をデコードすると、「fg」が 3 回得られます。

方法1

この方法では 2 つのスタックを使用して問題を解決します。開き括弧を取得したら、それをスタックにプッシュします。さらに、数値を取得すると、すべての数値を有効な正の整数に追加し、整数スタックに追加します。その後、閉じ括弧を取得したら、スタックから整数と文字をポップします。 ＃＃＃アルゴリズム＃＃＃

ステップ 1

- 数値を格納する「instSt」スタックと、文字列文字と左括弧を格納する「strSt」スタックを定義します。さらに、「answer」は結果文字列を格納するために初期化され、「tempStr」は一時文字列を格納するために初期化されます。

ステップ 2

- 文字列のトラバースを開始します。

ステップ 3

- 現在の文字が数字の場合は、「num」を 0 で初期化し、数字を保存します。

ステップ 3.1

- pthth インデックスの文字が数字の場合は、英字または括弧が見つかるまで文字列をたどります。ループ内で、「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」文字列に追加してそれを返します。

＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量- O(n^2)。文字列を反復処理し、要素をスタックにプッシュおよびポップし続けるためです。

空間複雑度- スタックに要素を格納するには O(n)。

方法 2 この方法ではスタックを使わずに問題を解決します。さらに、 reverse() メソッドを使用して文字列を反転します。

＃＃＃アルゴリズム＃＃＃

ステップ 1- 文字列の反復を開始します。

ステップ 2- i 番目の文字が「]」の場合、それを「回答」文字列にプッシュします。それ以外の場合は、以下の手順に従ってください。

ステップ 3 - 「temp_Str」を空の文字列で初期化します。

ステップ 4 - 文字列が空になるか、「[」文字が見つかるまで、「answer」文字列の反復処理を続けます。また、「answer」文字列から最後の文字をポップし、それを「temp_Str」文字列に追加し続けます。

ステップ 5

- 「]」括弧が見つかった場所から逆方向に進み、「temp_Str」文字列を反転します。

ステップ 6 - 「回答」文字列から最後の文字を削除して、「[」文字を削除します。

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

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

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

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

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

示例

#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) 来存储数字和临时字符串。

以上がカウントとそれに続く部分文字列としてエンコードされた文字列を再帰的にデコードしますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。