# Decode String – Javascript

I’m trying to implement the Decode String algorithm in javascript.

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

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”

Example 4:

Input: s = “abc3[cd]xyz” Output: “abccdcdcdxyz”

My attempt:

```var decodeString = function(s) {
if(!s || s.length === 0)    return "";

let map = {
'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6,
'7': 7, '8': 8, '9': 9
};
let res = "";

const dfs = (str) => {
//let res = "";
const arr = str.split("");
for(let i=0; i<arr.length; i++) {
if(arr[i] === '[') {
// call dfs
const close = getClosePos(i, arr);
dfs(arr.splice(i+1,close-(i+1)).join(""));
} else if(map[arr[i]] !== undefined) {
// repet N next letters
let k = map[arr[i]];
while(k > 0) {
res += dfs(arr.splice(i+1,arr.length).join(""));
k--;
}
} else if(arr[i] !== ']') {
res += arr[i];
}
}
//return res;
}
dfs(s);

return res;
};

const getClosePos = (i, arr) => {
for(let j=i; j<arr.length; j++) {
if(arr[j] === ']')
return j;
}
return 0;
}
```

My output is: `"undefinedundefinedundefined"`

Thanks

This answer is creative and good; we can also use stack for solving this problem.

This’ll get accepted:

```const decodeString = s => {
const stack = [];
for (const char of s) {
if (char !== "]") {
stack.push(char);
continue;
}

let currChar = stack.pop();
let decoded = '';
while (currChar !== '[') {
decoded = currChar.concat(decoded);
currChar = stack.pop();
}

let num = '';
currChar = stack.pop();

while (!Number.isNaN(Number(currChar))) {
num = currChar.concat(num);
currChar = stack.pop();
}

stack.push(currChar);
stack.push(decoded.repeat(Number(num)));
}

return stack.join('');
};

console.log(decodeString("3[a]2[bc]"))
console.log(decodeString("3[a2[c]]"))
console.log(decodeString("2[abc]3[cd]ef"))
console.log(decodeString("abc3[cd]xyz"))```

In Python, we would similarly use a list, which is very similar to JavaScript’s array:

```class Solution:
def decodeString(self, base_string):
stack = []
decoded = ''
full_num = 0

for char in base_string:
if char == '[':
stack.append(decoded)
stack.append(full_num)
decoded, full_num = '', 0
elif char == ']':
curr_digit, curr_char = stack.pop(), stack.pop()
decoded = curr_char + curr_digit * decoded
elif char.isdigit():
full_num *= 10
full_num += int(char)
else:
decoded += char

return decoded
```

In Java, we would have used two Stacks:

```class Solution {
public String decodeString(String string) {
String decoded = "";
Stack<Integer> numberStack = new Stack<>();
Stack<String> decodedStack = new Stack<>();
int count = 0;

while (count < string.length()) {
if (Character.isDigit(string.charAt(count))) {
int fullNum = 0;

while (Character.isDigit(string.charAt(count))) {
fullNum = 10 * fullNum + (string.charAt(count) - '0');
count++;
}

numberStack.push(fullNum);

} else if (string.charAt(count) == '[') {
decodedStack.push(decoded);
decoded = "";
count++;

} else if (string.charAt(count) == ']') {
StringBuilder temp = new StringBuilder(decodedStack.pop());
int repeatTimes = numberStack.pop();

for (int iter = 0; iter < repeatTimes; iter++)
temp.append(decoded);

decoded = temp.toString();
count++;

} else
decoded += string.charAt(count++);
}

return decoded;
}
}
```

## References

• For additional details, you can see the Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis1, 2 in there.
User contributions licensed under: CC BY-SA
7 People found this is helpful