[LeetCode] 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".

Thought process:
Recursively decode strings inside brackets and append them to result.

Solution 1 (Recursive):

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

class Solution { private int i = 0; public String decodeString(String s) { return decodeStringRecursive(s); } private String decodeStringRecursive(String s) { String decoded = ""; while (i < s.length() && s.charAt(i) != ']') { if (Character.isDigit(s.charAt(i))) { int n = 0; while (Character.isDigit(s.charAt(i))) { n = 10 * n + s.charAt(i) - '0'; i++; } i++; String str = decodeStringRecursive(s); while (n > 0) { decoded += str; n--; } } else { decoded += s.charAt(i); } i++; } return decoded; } }

The problem can also be solved iteratively using stack. Use one stack to keep track of numbers and another to keep track of strings. Iterate through the string. There are several cases:

1. Digit:
1. If numStack.size() == strStack.size(), there could be string which is not contained in brackets before the number. Append current buffer to result.
2. Use a while loop to read in all following digits.
2. Letter: append it to current buffer.
3. [:
1. Push number onto stack.
2. Push current buffer onto stack if numStack.size() > strStack.size().
4. ]:
1. Pop k from stack and repeat current buffer k times.
2. If stacks are empty, we can safely append current buffer to result.
3. Otherwise, pop the top buffer from strStack and append current buffer after it.

Solution 2 (Stack):

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 37 38 39 40 41 42 43 44 45 46 47 48 49 50

class Solution { public String decodeString(String s) { Stack<Integer> numStack = new Stack<>(); Stack<StringBuilder> strStack = new Stack<>(); StringBuilder sb = new StringBuilder(); StringBuilder current = new StringBuilder(); int k = 0; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (Character.isDigit(c)) { if (numStack.size() == strStack.size()) { sb.append(current.toString()); current = new StringBuilder(); } int j = i; while (Character.isDigit(s.charAt(j))) { j++; } k = Integer.parseInt(s.substring(i, j)); i = j - 1; } else if (Character.isLetter(c)) { current.append(c); } else if (c == '[') { numStack.push(k); if (numStack.size() > 1) { strStack.push(current); current = new StringBuilder(); } } else { k = numStack.pop(); String str = current.toString(); for (int j = 1; j < k; j++) { current = current.append(str); } if (strStack.isEmpty()) { sb.append(current.toString()); current = new StringBuilder(); } else { current = strStack.pop().append(current.toString()); } } } if (current.length() > 0) { sb.append(current.toString()); } return sb.toString(); } }

Time complexity: O(n).