Question

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

 394	Decode String

 Given an encoded string, return it's 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; 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 won't be input like 3a or 2[4].

 Examples:

 s = "3[a]2[bc]", return "aaabcbc".
 s = "3[a2[c]]", return "accaccacc".
 s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

 @tag-stack

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

Java

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]]"));
    }


    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();
        }
    }
}

// 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]

394 - Decode String

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions