Децоде Стринг


Ниво тешкоће Средњи
Често питани у амазонка јабука Блоомберг БитеДанце Цисцо еБаи фацебоок гоогле Хулу мицрософт пророчанство
Дубина прва претрага Стацк низ

Претпоставимо да сте добили кодирани низ. А. низ је кодиран у некаквом обрасцу, ваш задатак је декодирање низа.

Рецимо, <пута се низ не јавља> [стринг]

Пример

Улазни

3 [б] 2 [бц]

Излаз

бббцаца

Објашњење

Овде „Б“ јавља се 3 пута и „Ца“ јављају се 2 пута.

Улазни

2 [б2 [д]]

Излаз

бддбдд

Објашњење

Овде ће прво деловати у два дела и проширити се „Д“ 2 пута, па ће постати 2 [бдд], а ако поновимо ово два пута, биће бддбдд.

Алгоритам за низ декодирања

  1. Подесите темп и оутпут на празан низ, користићемо га касније привремено чувајући низове.
  2. Почевши од 0, док сам и мањи од дужине низа:
    проверите да ли је стр [и] једнак цифри, гурните је у цео низ.
  3. Иначе ако је стр [и] једнак било којем знаку, осим ']', гурните га у низ знакова.
  4. Ако је пронађено ']', избаците број из целог броја и избаците све знакове из скупа знакова и сачувајте га у привременом низу док се не пронађе '[' и искочи '['.
  5. Спремите и додајте вредност темп на излаз све док се број не искочи из целог броја.
  6. Из излазног низа гурните све знакове у низ знакова и поставите излаз на празан низ.
  7. Понављајте овај поступак све док сви знакови из лика стек и искачу цели бројеви из целог броја ().
  8. Искочите све знакове из скупа знакова и спремите их у излаз.
  9. Повратни излаз

Објашњење за низ декодирања

Добијамо низ који је декодиран у неком узорку, морамо га кодирати и вратити одговарајући низ који верификује декодирани низ, за ​​ово ћемо користити два различита стога. У један ћемо сместити целе бројеве, а у други низ, знакове.

Претпоставимо да нам је дат низ, 3 [б2 [ца]], то значи да треба да изнесе 2 пута ац што значи „цаца“, а сада ће се цонцат са б, тако да ће изнутра постати „бцаца“, а овај низ се јавља 3 пута па ће постати бцацабцацабцаца.

Узмимо пример

Пример низа декодирања

Улаз: 3 [б2 [ца]]

и = 0;

стр [и] = 3 гурнуће се у целобројни стек

и = 1;

стр [и] = '[' гура се у скуп знакова.

и = 2;

стр [и] = б, гура се у скуп знакова

и = 3;

стр [и] = '2' угураће се у целобројни стек.

и = 4;

стр [и] = '[', гура се у низ знакова

и = 5;

стр [и] = 'ц' гура се у скуп знакова.

и = 6;

стр [и] = 'а' гура се у скуп знакова.

и = 7;

стр [и] = ']' према алгоритму, ако нађемо ово ']', морамо ископати цео број из целог броја који је сада 2 и треба искочити карактер један по један и сачувати га у привременом низу из стог знакова док нисмо пронашли '[' овај лик и на крају испразнили овај знак.

Дакле, сада ће темп бити „ца“.

Помножићемо тај привремени низ више пута као број који смо искакали из целог броја, а то је ноОфИнтегер = 2 и сачувамо га за излаз.

Тако ће излаз Децоде Стринга постати "цаца" након што га унесемо, морамо га поново гурнути у стек знакова.

и = 8;

стр [и] = “]”, опет смо пронашли ово, потребно је да избацимо цео број из целог броја који је сада 3, а треба да искочимо знак један по један и сачувамо га у привременом низу из стека знакова док не пронађемо '[' овај лик и на крају поп овај лик.

Дакле, сада ће темп бити "бцаца".

Помножићемо тај привремени низ више пута као број који смо искакали из целог броја, а то је ноОфИнтегер = 3 и сачувамо га за излаз.

Тако ће излаз постати „бцацабцацабцаца“.

А након овога, дужина низа је достигнута, враћамо излаз.

Наш излаз биће: „бцацабцацабцаца“.

Децоде Стринг

 

Примена за низ декодирања

Програм Ц ++

#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

Илустрација горњег кода

Децоде Стринг

Анализа сложености

Сложеност времена

Овде сложеност времена није фиксна јер зависи од улазног низа јер сваки пут поновимо неки корак и спојимо низ

Сложеност простора

Он) где је н дужина низа. За примену користимо стек, а максимална могућа величина стека је н.

Референце