TK
Home

# Algorithms Problem Solving: Decode String Photo by Milad Fakurian

This post is part of the Algorithms Problem Solving series.

## Problem description

This is the Decode String problem. The description looks like this:

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

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

## Examples

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"
``````

## Solution

One of the possible solutions I came up with was to use a stack data structure to handle the data within the brackets. The basic idea is to iterate through all characters for each character, verify if it's a number, a `]` (closing bracket), or a normal string character (`[` included).

To iterate through the entire string, we can use a `while` with an index:

``````while (index < encodedString.length) {
index++;
}
``````

To verify if the character is a number, I built a simple function:

``````const isNum = (char) => !isNaN(Number(char));
``````

So if the character is a number, we push it to the stack. But the number can be more than just one digit, so we need to move to the next index until the character isn’t a number anymore.

``````if (isNum(char)) {
const number = [];

while (isNum(encodedString[index])) {
number.push(encodedString[index]);
index++;
}

stack.push(Number(number.join('')));
continue;
}
``````

I created a `number` array and push each number character into this list. After we get the whole number, we push it to the stack.

But if the character is a `]`, we need to get the whole string that was inside the brackets and we do it by using the `pop` method from the stack. We do it until it gets to the `[` character. Then we can `pop` it again to remove the `[` character. And finally, repeat the string x times and push it to the stack.

``````if (char === ']') {
let str = '';

while (stack[stack.length - 1] !== '[') {
str = stack.pop() + str;
}

stack.pop();
stack.push(str.repeat(stack.pop()));
index++;
continue;
}
``````

The `repeat` method is very interesting. I didn’t know about this method, so I usually do a loop that works fine too:

``````const repeatedString = [];
const str = 'hey';
let num = 3;

while (num > 0) {
repeatedString.push(str);
num--;
}

repeatedString.join(''); // 'heyheyhey'
``````

Using repeat is so much simpler and more convenient for this problem.

``````const str = 'hey';
const num = 3;

str.repeat(num); // 'heyheyhey'
``````

And finally, if it isn't a `]` and number, just push the character to the stack and increment the index:

``````stack.push(char);
index++;
``````

The whole implementation looks like this:

``````const isNum = (char) => !isNaN(Number(char));

function decodeString(encodedString) {
const stack = [];
let index = 0;

while (index < encodedString.length) {
const char = encodedString[index];

if (isNum(char)) {
const number = [];

while (isNum(encodedString[index])) {
number.push(encodedString[index]);
index++;
}

stack.push(Number(number.join('')));
continue;
}

if (char === ']') {
let str = '';

while (stack[stack.length - 1] !== '[') {
str = stack.pop() + str;
}

stack.pop();
stack.push(str.repeat(stack.pop()));
index++;
continue;
}

stack.push(char);
index++;
}

return stack.join('');
}
``````