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
Advertisement
Answer
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;
}
}