문자열 디코딩

난이도 중급
자주 묻는 질문 아마존 Apple 블룸버그 게시물에서 ByteDance 시스코 이베이 Facebook 구글 훌루 Microsoft 신탁
깊이 우선 검색 스택 조회수 43

인코딩 된 문자열이 주어진다고 가정합니다. ㅏ 어떤 패턴으로 인코딩 된 경우 문자열을 디코딩해야합니다.

<문자열 발생 횟수> [문자열]

입력

3 [b] 2 [bc]

산출

bbccaca

설명

여기로 "비" 3 회 발생하고 "ca" 2 번 발생합니다.

입력

2 [b2 [d]]

산출

bddbdd

설명

여기에서는 두 부분으로 먼저 작동합니다. "디" 2 번 반복하면 2 [bdd]가되고 두 ​​번 반복하면 bddbdd가됩니다.

디코딩 문자열 알고리즘

  1. 임시 및 출력을 빈 문자열로 설정하면 나중에 일시적으로 문자열을 저장하는 데 사용할 것입니다.
  2. 0부터 시작하여 문자열 길이보다 작습니다.
    str [i]가 숫자와 같은지 확인하고 정수 스택으로 푸시합니다.
  3. 그렇지 않으면 str [i]가 ']'를 제외한 모든 문자와 같으면 문자 스택으로 푸시합니다.
  4. ']'가 발견되면 정수 스택에서 숫자를 팝하고 문자 스택의 모든 문자를 팝하고 '['가 발견되고 '['가 팝될 때까지 임시 문자열에 저장합니다.
  5. 정수 스택에서 숫자가 나올 때까지 출력 할 temp 값을 저장하고 추가합니다.
  6. 출력 문자열에서 모든 문자를 문자 스택으로 푸시하고 출력을 빈 문자열로 설정합니다.
  7. 캐릭터의 모든 캐릭터가 나올 때까지이 과정을 반복합니다. 스택 정수 스택의 정수가 popped ()됩니다.
  8. 문자 스택에서 모든 문자를 꺼내 출력에 저장합니다.
  9. 반환 출력

디코딩 문자열에 대한 설명

어떤 패턴으로 디코딩 된 문자열이 주어졌고,이를 인코딩하고 디코딩 된 문자열을 확인하는 적절한 문자열을 반환해야합니다.이를 위해 두 개의 다른 스택을 사용할 것입니다. 하나에는 정수를 저장하고 다른 스택에는 문자를 저장합니다.

3 [b2 [ca]]라는 문자열이 주어 졌다고 가정합니다. 이것은 "caca"를 의미하는 ac를 2 번 출력해야 함을 의미하고 이제 b와 연결되므로 내부에서 "bcaca"가되고이 문자열은 3 번 발생합니다. 그래서 그것은 bcacabcacabcaca가 될 것입니다.

예를 들어 보자

디코딩 문자열의 예

입력 : 3 [b2 [ca]]

i = 0;

str [i] = 3 정수 스택으로 푸시합니다.

i = 1;

str [i] = '['문자 스택으로 푸시됩니다.

i = 2;

str [i] = b, 문자 스택으로 푸시됩니다.

i = 3;

str [i] = '2'정수 스택으로 푸시합니다.

i = 4;

str [i] = '[', 문자 스택으로 푸시됩니다.

i = 5;

str [i] = 'c'문자 스택으로 푸시됩니다.

i = 6;

str [i] = 'a'문자 스택으로 푸시됩니다.

i = 7;

str [i] = ']'알고리즘에 따라이 ']'를 찾으면 이제 2 인 정수 스택에서 정수를 꺼내야하며 문자를 하나씩 꺼내어 임시 문자열에 저장해야합니다. '['이 문자를 발견하고 마침내이 문자를 팝할 때까지 문자 스택.

이제 temp는 "ca"가됩니다.

그 임시 문자열을 정수 스택에서 뽑은 숫자와 noOfInteger = 2로 곱하여 출력에 저장합니다.

따라서 Decode String의 출력은 입력 후 "caca"가됩니다. 문자 스택으로 다시 푸시해야합니다.

i = 8;

str [i] =“]”, 다시 이것을 찾았습니다. 이제 3 인 정수 스택에서 정수를 꺼내야합니다. 문자를 하나씩 꺼내어 찾을 때까지 문자 스택에서 임시 문자열에 저장해야합니다. '['이 캐릭터와 마침내이 캐릭터를 팝니다.

이제 temp는 "bcaca"가됩니다.

그 임시 문자열을 정수 스택에서 뽑은 숫자와 noOfInteger = 3로 곱하여 출력에 저장합니다.

따라서 출력은 "bcacabcacabcaca"가됩니다.

그 후 문자열의 길이에 도달하면 출력이 반환됩니다.

출력은“bcacabcacabcaca”입니다.

문자열 디코딩

 

디코딩 문자열 구현

C ++ 프로그램

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

string getDecodeString(string str)
{
    stack<int> pushInt ;
    stack<char> charStack ;
    string temp = "";
    string output = "";

    for (int i = 0; i < str.length(); i++)
    {
        int noOfInteger = 0;
        if (isdigit(str[i]))
        {
            while (isdigit(str[i]))
            {
                noOfInteger = noOfInteger * 10 + str[i] - '0';
                i++;
            }

            i--;
            pushInt.push(noOfInteger);
        }
        else if (str[i] == ']')
        {
            temp = "";
            noOfInteger = 0;

            if (!pushInt.empty())
            {
                noOfInteger = pushInt.top();
                pushInt.pop();
            }

            while (!charStack.empty() && charStack.top()!='[' )
            {
                temp = charStack.top() + temp;
                charStack.pop();
            }
            if (!charStack.empty() && charStack.top() == '[')
            {
                charStack.pop();
            }
            for (int j = 0; j < noOfInteger; j++)
            {
                output = output + temp;
            }
            for (int j = 0; j < output.length(); j++)
            {
                charStack.push(output[j]);
            }
            output = "";
        }
        else if (str[i] == '[')
        {
            if (isdigit(str[i-1]))
            {
                charStack.push(str[i]);
            }
            else
            {
                charStack.push(str[i]);
                pushInt.push(1);
            }
        }
        else
        {
            charStack.push(str[i]);
        }
    }
    while (!charStack.empty())
    {
        output = charStack.top() + output;
        charStack.pop();
    }
    return output;
}
int main()
{
    string str = "3[b2[ca]]";
    cout<<getDecodeString(str);
    return 0;
}
bcacabcacabcaca

자바 프로그램

import java.util.Stack;
class stringDecoding
{
    static String getDecodeString(String str)
    {
        Stack<Integer> pushInt = new Stack<>();
        Stack<Character> charStack = new Stack<>();
        String temp = "";
        String output = "";

        for (int i = 0; i < str.length(); i++)
        {
            int noOfInteger = 0;
            if (Character.isDigit(str.charAt(i)))
            {
                while (Character.isDigit(str.charAt(i)))
                {
                    noOfInteger = noOfInteger * 10 + str.charAt(i) - '0';
                    i++;
                }

                i--;
                pushInt.push(noOfInteger);
            }
            else if (str.charAt(i) == ']')
            {
                temp = "";
                noOfInteger = 0;

                if (!pushInt.isEmpty())
                {
                    noOfInteger = pushInt.peek();
                    pushInt.pop();
                }

                while (!charStack.isEmpty() && charStack.peek()!='[' )
                {
                    temp = charStack.peek() + temp;
                    charStack.pop();
                }

                if (!charStack.empty() && charStack.peek() == '[')
                {
                    charStack.pop();
                }

                for (int j = 0; j < noOfInteger; j++)
                {
                    output = output + temp;
                }

                for (int j = 0; j < output.length(); j++)
                {
                    charStack.push(output.charAt(j));
                }

                output = "";
            }
            else if (str.charAt(i) == '[')
            {
                if (Character.isDigit(str.charAt(i-1)))
                {
                    charStack.push(str.charAt(i));
                }
                else
                {
                    charStack.push(str.charAt(i));
                    pushInt.push(1);
                }
            }

            else
            {
                charStack.push(str.charAt(i));
            }
        }
        while (!charStack.isEmpty())
        {
            output = charStack.peek() + output;
            charStack.pop();
        }

        return output;
    }
    public static void main(String args[])
    {
        String str = "3[b2[ca]]";
        System.out.println(getDecodeString(str));
    }
}
bcacabcacabcaca

위 코드 그림

문자열 디코딩

복잡성 분석

시간 복잡성

여기서 시간 복잡도는 입력 문자열에 따라 달라지기 때문에 고정되지 않습니다. 매 단계를 반복하고 문자열을 연결할 때마다

공간 복잡성

O (N) 여기서 n은 문자열의 길이입니다. 구현을 위해 스택을 사용하고 스택의 가능한 최대 크기는 n입니다.

참조

Translate »