카운트 뒤에 하위 문자열이 따라오는 방식으로 인코딩된 문자열을 재귀적으로 디코딩합니다.

이 문제에서는 총 횟수를 반복적으로 더하여 주어진 문자열을 디코딩해야 합니다.

우리는 세 가지 다른 방식으로 문제에 접근할 수 있으며 문제를 해결하기 위해 두 개의 스택 또는 하나의 스택을 사용할 수 있습니다. 또한 두 개의 스택을 사용하지 않고도 문제를 해결할 수 있습니다.

문제 설명 - 왼쪽 및 오른쪽 대괄호, 영문자 및 ​​숫자가 포함된 문자열 str이 제공됩니다. 문자열을 재귀적으로 디코딩해야 합니다.

다음은 문자열을 디코딩하는 패턴이나 규칙입니다.

• [chars] - "chars"는 결과 문자열에 횟수만큼 표시되어야 합니다.

예

들어가세요

으아악

출력

으아악

지침

• 먼저 2[n]을 디코딩하여 "2[d]3[cnn]"을 얻습니다.

• 다음으로 3[cnn]을 디코딩합니다. 그래서 우리는 "2[d]cnnncnncnn"을 얻습니다.

• 다음으로 2[d]를 디코딩합니다. 그래서 우리는 "ddcnnncnncnn"을 얻습니다.

들어가세요

으아악

출력

으아악

설명- 주어진 문자열을 해독하면 5개의 "I"를 얻습니다.

들어가세요

으아악

출력

으아악

설명- 입력 문자열을 디코딩하면 "fg"가 3번 나옵니다.

방법 1

이 방법에서는 두 개의 스택을 사용하여 문제를 해결합니다. 여는 괄호를 얻으면 이를 스택에 푸시합니다. 또한 숫자 문자를 얻을 때 모든 숫자 문자를 유효한 양의 정수에 추가하고 이를 정수 스택에 추가합니다. 나중에 닫는 괄호를 얻으면 스택에서 정수와 문자를 팝합니다.

알고리즘

1단계 - "instSt" 스택을 정의하여 숫자를 저장하고 "strSt"를 정의하여 문자열 문자와 왼쪽 대괄호를 저장하세요. 또한 "응답"은 결과 문자열을 저장하도록 초기화되고 "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" "num"번을 추가해야 합니다.

4.5단계 - "답변" 문자열의 각 문자를 "strSt" 스택에 삽입하고 빈 문자열로 다시 초기화합니다.

5단계 − 현재 문자가 왼쪽 괄호인 경우 다음 단계를 따르세요.

5.1단계 − 이전 문자가 숫자인 경우 "["를 스택 "StrSt"에 푸시합니다. 그렇지 않으면 "["를 StrSt 스택에 푸시하고 1을 "instSt" 스택에 푸시합니다.

6단계− 알파벳 문자를 얻으면 "strSt" 스택에 푸시합니다.

7단계 - 마지막으로 루프를 사용하여 "strSt" 스택에서 모든 문자를 제거하고 "답변" 문자열에 추가한 후 반환합니다.

예

으아악

출력

으아악

시간 복잡도− O(n^2) 왜냐하면 문자열을 반복하면서 스택에 요소를 계속해서 밀고 터뜨리기 때문입니다.

Space Complexity− 스택에 요소를 저장하기 위한 O(n)입니다.

방법 2

이 방법에서는 스택을 사용하지 않고 문제를 해결해 보겠습니다. 또한 reverse() 메서드를 사용하여 문자열을 반전합니다.

알고리즘

1단계 - 문자열 반복을 시작합니다.

2단계− i번째 문자가 "]"인 경우 "답변" 문자열에 삽입합니다. 그렇지 않은 경우 아래 단계를 따르세요.

3단계 - 빈 문자열로 "temp_Str"을 초기화합니다.

4단계 - 문자열이 비어 있거나 "[" 문자가 발견될 때까지 "답변" 문자열을 계속 반복합니다. 또한 "답변" 문자열에서 마지막 문자를 계속해서 꺼내어 "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 중국어 웹사이트의 기타 관련 기사를 참조하세요!