Welcome to Subscribe On Youtube
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 105
.
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; }