Question

Formatted question description: https://leetcode.ca/all/394.html

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].

The test cases are generated so that the length of the output will never exceed 10⁵.

Example 1:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Example 2:

Input: s = "3[a2[c]]"
Output: "accaccacc"

Example 3:

Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Constraints:

1 <= s.length <= 30
s consists of lowercase English letters, digits, and square brackets '[]'.
s is guaranteed to be a valid input.
All the integers in s are in the range [1, 300].

Algorithm

Questions:

nested allowed? yes, 3[a2[c]]
count could be overflowed

Use stack to assist calculation, we use two stacks,

One is used to store the number,
One to save the string,

Traverse the input string,

If we encounter a number, we update the count variable cnt;
If you encounter a left parenthesis, we push the current cnt into the number stack, and push the current t into the string stack;
If we encounter the right parenthesis, we take out the top element in the number stack and store it in the variable k, then add k t strings to the top element of the string stack, and then take the top element and store it in the string t;
If we encounter a letter, we directly add it to the string t

Code

import java.util.Stack;

public class Decode_String {

    public static void main(String[] args) {
        Decode_String out = new Decode_String();
        Solution s = out.new Solution();

//        System.out.println(s.decodeString("3[a]2[bc]"));
        System.out.println(s.decodeString("3[a2[c]]"));
    }

    class Solution_cleaner {
        public String decodeString(String s) {
            Stack<Integer> s1 = new Stack<>();
            Stack<String> s2 = new Stack<>();
            int num = 0;
            String res = "";
            for (char c : s.toCharArray()) {
                if (Character.isDigit(c)) {
                    num = num * 10 + Character.getNumericValue(c);
                } else if (c == '[') {
                    s1.push(num);
                    s2.push(res);
                    num = 0;
                    res = "";
                } else if (c == ']') {
                    res = s2.pop() + String.join("", Collections.nCopies(s1.pop(), res));
                } else {
                    res += c;
                }
            }
            return res;
        }
    }

    public class Solution {
        public String decodeString(String s) {
            String res = "";
            Stack<Integer> countStack = new Stack<>();
            Stack<String> resStack = new Stack<>();
            int idx = 0;
            while (idx < s.length()) {
                if (Character.isDigit(s.charAt(idx))) {
                    int count = 0;
                    while (Character.isDigit(s.charAt(idx))) {
                        count = 10 * count + (s.charAt(idx) - '0');
                        idx++;
                    }
                    countStack.push(count);
                } else if (s.charAt(idx) == '[') {
                    resStack.push(res);
                    res = "";
                    idx++;
                } else if (s.charAt(idx) == ']') {
                    StringBuilder temp = new StringBuilder(resStack.pop());
                    int repeatTimes = countStack.pop();
                    for (int i = 0; i < repeatTimes; i++) {
                        temp.append(res);
                    }
                    res = temp.toString();
                    idx++;
                } else {
                    res += s.charAt(idx++);
                }
            }
            return res;
        }
    }


    class Solution2 {

        /*
            questions:

            1. nested?
                yes, "3[a2[c]]"
            2. count could be overflowed
         */
        public String decodeString(String s) {

            StringBuilder result = new StringBuilder();

            Stack<Integer> countSk = new Stack<>();
            Stack<String> segSk = new Stack<>();

            int i = 0;
            while (i < s.length()) {

                // parse count
                int countProbe = i;
                while (Character.isDigit(s.charAt(countProbe))) {
                    countProbe++;
                }
                int count = Integer.valueOf(s.substring(i, countProbe));
                countSk.push(count);

                // parse segment
                i = countProbe;
                if (s.charAt(i) != '[') {
                    return null;
                }
                i++; // move to first char after [
                int segProbe = i;

                // stuck here, checking '[' and push and continue another while loop
                //          wont continue, since the code is ugly anyway
                while (s.charAt(segProbe) != ']') {
                    segProbe++;
                }
                String seg = s.substring(i, segProbe);
                segSk.push(seg);

                // process encountering ']'
                int thisCount = countSk.pop();
                String thisSeg = segSk.pop();
                String tmp = "";
                while (thisCount > 0) {
                    thisCount--;
                    tmp += thisSeg;
                }
                if (!segSk.isEmpty()) {
                    segSk.push(segSk.pop() + tmp);
                } else {
                    segSk.push(tmp);
                }

                i = segProbe;
                i++; // move to next count-segment block

            }

            return segSk.pop();
        }
    }
}

############

class Solution {
    public String decodeString(String s) {
        Deque<Integer> s1 = new ArrayDeque<>();
        Deque<String> s2 = new ArrayDeque<>();
        int num = 0;
        String res = "";
        for (char c : s.toCharArray()) {
            if ('0' <= c && c <= '9') {
                num = num * 10 + c - '0';
            } else if (c == '[') {
                s1.push(num);
                s2.push(res);
                num = 0;
                res = "";
            } else if (c == ']') {
                StringBuilder t = new StringBuilder();
                for (int i = 0, n = s1.pop(); i < n; ++i) {
                    t.append(res);
                }
                res = s2.pop() + t.toString();
            } else {
                res += String.valueOf(c);
            }
        }
        return res;
    }
}

// OJ: https://leetcode.com/problems/decode-string/
// Time: O(N)
// Space: O(N)
class Solution {
    string decodeString(string &s, int &i) {
        int N = s.size();
        string ans;
        while (i < N && s[i] != ']') {
            if (isdigit(s[i])) {
                int repeat = 0;
                while (i < N && isdigit(s[i])) repeat = repeat * 10 + (s[i++] - '0');
                ++i; // skip [
                auto t = decodeString(s, i);
                ++i; // skip ]
                while (repeat--) ans += t;
            } else {
                ans += s[i++];
            }
        }
        return ans;
    }
public:
    string decodeString(string s) {
        int i = 0;
        return decodeString(s, i);
    }
};

class Solution:
    def decodeString(self, s: str) -> str:
        s1, s2 = [], []
        num, res = 0, ''
        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)
            elif c == '[':
                s1.append(num)
                s2.append(res) # initial, res being pushed is empty str ''
                num, res = 0, ''
            elif c == ']':
                res = s2.pop() + res * s1.pop()
            else:
                res += c
        return res

############

class Solution(object):
  def decodeString(self, s):
    """
    :type s: str
    :rtype: str
    """
    num = ""
    stack = [["", 1]]
    for c in s:
      if c in "0123456789":
        num += c
      elif c == "[":
        stack.append(["", int(num)])
        num = ""
      elif c == "]":
        ss, k = stack.pop()
        stack[-1][0] += ss * k
      else:
        stack[-1][0] += c
    return stack[-1][0]

function decodeString(s: string): string {
    let ans = '';
    let stack = [];
    let count = 0; // repeatCount
    for (let cur of s) {
        if (/[0-9]/.test(cur)) {
            count = count * 10 + Number(cur);
        } else if (/[a-z]/.test(cur)) {
            ans += cur;
        } else if ('[' == cur) {
            stack.push([ans, count]);
            // reset
            ans = '';
            count = 0;
        } else {
            // match ']'
            let [pre, count] = stack.pop();
            ans = pre + ans.repeat(count);
        }
    }
    return ans;
}

394 - Decode String

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions