LeetCode Solutions

Time: $O(|\texttt{ans}|)$

Space: $O(|\texttt{ans}|)$

			

class Solution {
 public:
  string decodeString(string s) {
    stack<pair<string, int>> stack;  // (prevStr, repeatCount)
    string currStr;
    int currNum = 0;

    for (const char c : s)
      if (isdigit(c)) {
        currNum = currNum * 10 + (c - '0');
      } else {
        if (c == '[') {
          stack.emplace(currStr, currNum);
          currStr = "";
          currNum = 0;
        } else if (c == ']') {
          const auto [prevStr, n] = stack.top();
          stack.pop();
          currStr = prevStr + getRepeatedStr(currStr, n);
        } else {
          currStr += c;
        }
      }

    return currStr;
  }

 private:
  // S * n times
  string getRepeatedStr(const string& s, int n) {
    string repeat;
    while (n--)
      repeat += s;
    return repeat;
  }
};

			

class Solution {
  public String decodeString(String s) {
    Stack<Pair<StringBuilder, Integer>> stack = new Stack<>(); // (prevStr, repeatCount)
    StringBuilder currStr = new StringBuilder();
    int currNum = 0;

    for (final char c : s.toCharArray())
      if (Character.isDigit(c)) {
        currNum = currNum * 10 + (c - '0');
      } else {
        if (c == '[') {
          stack.push(new Pair<>(currStr, currNum));
          currStr = new StringBuilder();
          currNum = 0;
        } else if (c == ']') {
          final Pair<StringBuilder, Integer> pair = stack.pop();
          final StringBuilder prevStr = pair.getKey();
          final int n = pair.getValue();
          currStr = prevStr.append(getRepeatedStr(currStr, n));
        } else {
          currStr.append(c);
        }
      }

    return currStr.toString();
  }

  // S * n times
  private StringBuilder getRepeatedStr(StringBuilder s, int n) {
    StringBuilder sb = new StringBuilder();
    while (n-- > 0)
      sb.append(s);
    return sb;
  }
}

			

class Solution:
  def decodeString(self, s: str) -> str:
    stack = []  # (prevStr, repeatCount)
    currStr = ''
    currNum = 0

    for c in s:
      if c.isdigit():
        currNum = currNum * 10 + int(c)
      else:
        if c == '[':
          stack.append((currStr, currNum))
          currStr = ''
          currNum = 0
        elif c == ']':
          prevStr, num = stack.pop()
          currStr = prevStr + num * currStr
        else:
          currStr += c

    return currStr