Problem of The Day: Decode String

Problem Statement

leetcode problem link

Need to review

Solution in C#

public class Solution
{
    public string DecodeString(string s)
    {
        var countStack = new Stack<int>();
        var stringStack = new Stack<StringBuilder>();
        var current = new StringBuilder();
        int k = 0;

        foreach (char c in s)
        {
            if (char.IsDigit(c))
            {
                // build multi-digit number
                k = k * 10 + (c - '0');
            }
            else if (c == '[')
            {
                countStack.Push(k);
                stringStack.Push(current);

                current = new StringBuilder();
                k = 0;
            }
            else if (c == ']')
            {
                int repeat = countStack.Pop();
                var prev = stringStack.Pop();

                for (int i = 0; i < repeat; i++)
                {
                    prev.Append(current);
                }

                current = prev;
            }
            else
            {
                current.Append(c);
            }
        }

        return current.ToString();
    }
}

Editorial

Approach 1: Using Stack

class Solution {
public:
    string decodeString(string s) {
        stack<char> st;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == ']') {
                string decodedString;
                // get the encoded string (in reverse order from stack)
                while (st.top() != '[') {
                    decodedString.push_back(st.top());
                    st.pop();
                }
                // pop '[' from stack
                st.pop();

                // get the number k
                int base = 1;
                int k = 0;
                while (!st.empty() && isdigit(st.top())) {
                    k += (st.top() - '0') * base;
                    st.pop();
                    base *= 10;
                }

                // decodedString is reversed, so fix it
                reverse(decodedString.begin(), decodedString.end());

                // push decodedString k times into stack
                while (k-- > 0) {
                    for (char c : decodedString) {
                        st.push(c);
                    }
                }
            } else {
                st.push(s[i]);
            }
        }

        // build result from stack
        string result;
        result.reserve(st.size());
        while (!st.empty()) {
            result.push_back(st.top());
            st.pop();
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

Approach 2: Using 2 Stack

class Solution {
public:
    string decodeString(string s) {
        stack<int> countStack;
        stack<string> stringStack;
        string currentString;
        int k = 0;
        for (auto ch : s) {
            if (isdigit(ch)) {
                k = k * 10 + ch - '0';
            } else if (ch == '[') {
                // push the number k to countStack
                countStack.push(k);
                // push the currentString to stringStack
                stringStack.push(currentString);
                // reset currentString and k
                currentString = "";
                k = 0;
            } else if (ch == ']') {
                string decodedString = stringStack.top();
                stringStack.pop();
                // decode currentK[currentString] by appending currentString k times
                for (int currentK = countStack.top(); currentK > 0; currentK--) {
                    decodedString = decodedString + currentString;
                }
                countStack.pop();
                currentString = decodedString;
            } else {
                currentString = currentString + ch;
            }
        }
        return currentString;
    }
};

Approach 3: Using Recursion

class Solution {
public:
    string decodeString(string s) {
        int index = 0;
        return decodeString(s, index);
    }
    string decodeString(const string& s, int& index) {
        string result;
        while (index < s.length() && s[index] != ']') {
            if (!isdigit(s[index]))
                result += s[index++];
            else {
                int k = 0;
                // build k while next character is a digit
                while (index < s.length() && isdigit(s[index]))
                    k = k * 10 + s[index++] - '0';
                // ignore the opening bracket '['
                index++;
                string decodedString = decodeString(s, index);
                // ignore the closing bracket ']'
                index++;
                while (k-- > 0)
                    result += decodedString;
            }
        }
        return result;
    }
};