解碼字符串


難度級別
經常問 亞馬遜 蘋果 彭博社 ByteDance 思科 易趣 Facebook 谷歌 葫蘆 Microsoft微軟 神諭
深度優先搜索

假設給了您一個編碼的字符串。 一種 以某種模式編碼,您的任務是解碼字符串。

讓我們說,<字符串不出現的次數> [string]

輸入

3 [b] 2 [bc]

產量

巴布卡卡

解釋

這裡 “ b” 發生3次並 “ ca” 發生2次。

輸入

2 [b2 [d]]

產量

天涯海角

解釋

在這裡它將分為兩個部分工作,首先是擴展 “ d” 2次,因此它將變為2 [bdd],然後如果我們重複兩次,它將為bddbdd。

字符串解碼算法

  1. 設置temp並將其輸出為空字符串,稍後我們將使用它臨時存儲字符串。
  2. 從0開始,而我小於字符串長度:
    檢查str [i]是否等於數字,將其壓入整數堆棧。
  3. 否則,如果str [i]等於除']'以外的任何其他字符,則將其壓入字符堆棧。
  4. 如果找到']',則從整數堆棧中彈出數字,並從字符堆棧中彈出所有字符,並將其存儲到臨時字符串中,直到找到'[',然後彈出'['。
  5. 存儲並添加temp的值以輸出,直到該數字從整數堆棧中彈出。
  6. 從輸出字符串中,將所有字符推入字符堆棧,然後將輸出設置為空字符串。
  7. 重複此過程,直到字符中的所有字符為止 和來自整數堆棧的整數被popped()。
  8. 從字符堆棧中彈出所有字符,並將其存儲到輸出中。
  9. 返回輸出

解碼字符串的說明

我們給了一個以某種模式解碼的字符串,我們必須對其進行編碼,然後返回一個合適的字符串來驗證解碼後的字符串,為此,我們將使用兩個不同的堆棧。 在其中一個中,我們將存儲整數,而在其他堆棧中,將存儲字符。

假設我們給定一個字符串3 [b2 [ca]],這意味著它應該輸出2倍的ac,這意味著“ caca”,現在它與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的整數堆棧中彈出整數,我們需要一個一個地彈出字符並將其存儲到臨時字符串中直到我們找到'['這個字符,最後彈出這個字符。

因此,現在溫度將為“ ca”。

我們將這個臨時字符串的數目乘以從整數堆棧中彈出的數目的次數,即noOfInteger = 2的次數,然後將其存儲到輸出中。

因此,將解碼字符串的輸出放入後,它將變為“ caca”,我們需要將其再次推入字符堆棧。

i = 8;

str [i] =“]”,我們再次發現了這一點,我們需要從現在為3的整數堆棧中彈出整數,並且需要一個一個地彈出字符並將其存儲到字符堆棧中的臨時字符串中,直到找到'['這個字符,最後彈出這個字符。

因此,現在溫度將為“ 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

Java程序

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。

參考