Skip to content

394. Decode String 👍

Approach 1: Stack

  • Time: $O(|\texttt{ans}|)$
  • Space: $O(|\texttt{ans}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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:
  // Returns s * n.
  string getRepeatedStr(const string& s, int n) {
    string repeat;
    while (n--)
      repeat += s;
    return repeat;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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();
  }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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

Approach 2: Recursive

  • Time: $O(|\texttt{ans}|)$
  • Space: $O(|\texttt{ans}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  string decodeString(string s) {
    string ans;

    while (i < s.length() && s[i] != ']')
      if (isdigit(s[i])) {
        int k = 0;
        while (i < s.length() && isdigit(s[i]))
          k = k * 10 + (s[i++] - '0');
        ++i;  // '['
        const string& decodedString = decodeString(s);
        ++i;  // ']'
        while (k-- > 0)
          ans += decodedString;
      } else {
        ans += s[i++];
      }

    return ans;
  }

 private:
  int i = 0;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public String decodeString(String s) {
    StringBuilder sb = new StringBuilder();

    while (i < s.length() && s.charAt(i) != ']')
      if (Character.isDigit(s.charAt(i))) {
        int k = 0;
        while (i < s.length() && Character.isDigit(s.charAt(i)))
          k = k * 10 + (s.charAt(i++) - '0');
        ++i; // '['
        final String decodedString = decodeString(s);
        ++i; // ']'
        while (k-- > 0)
          sb.append(decodedString);
      } else {
        sb.append(s.charAt(i++));
      }

    return sb.toString();
  }

  private int i = 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
  def decodeString(self, s: str) -> str:
    ans = ''

    while self.i < len(s) and s[self.i] != ']':
      if s[self.i].isdigit():
        k = 0
        while self.i < len(s) and s[self.i].isdigit():
          k = k * 10 + int(s[self.i])
          self.i += 1
        self.i += 1  # '['
        decodedString = self.decodeString(s)
        self.i += 1  # ']'
        ans += k * decodedString
      else:
        ans += s[self.i]
        self.i += 1

    return ans

  i = 0