Problem

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

Examples

Example 1:

1
2

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

Example 2:

1
2

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

Example 3:

1
2

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

Solution

Nested bracket looks like a bit of problem and solution. In eg. 2, we have 3[a2[c]] = 3[acc]. So, Basically we have to first multiply string with most nested bracket, and then outer bracket. This points to recursive or stack usage.

Method 1 - Using Stack

So, we can take a stack. Now consider the string - s = 54[ab6[cd]] We will keep on adding the chars to stack, till we find closing ], because that is the time we have to solve the problem.

So, we iterate on s:

Now, we encounter first closing parenthesis ].So, we pop out all chars till we find opening parenthesis [. So, we pop out cd from stack.

Now, we keep popping from stack till chars are digit. We get 6 is number, and multiply cd by 6 and put it back in stack, i.e. 6*cd.

Now we continue again, and we get last ], so now we have 54*(ab+6(cd)) as answer.

Code

 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

public String decodeString(String s) {

	Stack<Character> stack = new Stack<>();

	for (char c: s.toCharArray()) {
		if (c != ']') {
			stack.push(c); //push everything but ]
		} else {
			//step 1: 
			//if you find a closing ] then 
			//retrieve the string it encapsulates
			StringBuilder sb = new StringBuilder();
			while (!stack.isEmpty() && Character.isLetter(stack.peek()))
				sb.insert(0, stack.pop());

			String sub = sb.toString(); //this is the string contained in [ ]
			stack.pop(); //Discard the '[';

			//step 2: 
			//after that get the number of
			// times it should repeat from stack

			sb = new StringBuilder();
			while (!stack.isEmpty() && Character.isDigit(stack.peek()))
				sb.insert(0, stack.pop());

			int count = Integer.valueOf(sb.toString()); //this is the number

			//step 3: 
			//repeat the string within the [ ] count 
			//number of times and push it back into stack

			while (count > 0) {
				for (char ch: sub.toCharArray())
					stack.push(ch);
				count--;
			}
		}
	}

	//final fetching and returning the value in stack 
	StringBuilder retv = new StringBuilder();
	while (!stack.isEmpty())
		retv.insert(0, stack.pop());

	return retv.toString();
}
 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

public String decodeString(String s) {
	Stack<Integer> count = new Stack<>();
	Stack<String> result = new Stack<>();
	int i = 0;
	result.push("");
	while (i < s.length()) {
		char c = s.charAt(i);
		if (c >= '0' && c <= '9') {
			int start = i;
			while (s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9') i++;
			count.push(Integer.parseInt(s.substring(start, i + 1)));
		} else if (ch == '[') {
			result.push("");// push a new string
		} else if (ch == ']') {// update and multiply existing string
			String str = result.pop();
			
			StringBuilder sb = new StringBuilder();
			
			int times = count.pop();
			for (int j = 0; j < times; j += 1) {
				sb.append(str);
			}
			
			result.push(result.pop() + sb.toString());
		} else {
			result.push(result.pop() + ch); // update existing string
		}
		i += 1;
	}
	return result.pop();
}