Decode String
Problem
Decode a string encoded as k[encoded], meaning the part inside the brackets repeated k times. Brackets can be nested, and the input is always valid.
Example 1
Input: "3[a]2[bc]" Output: "aaabcbc"
Example 2
Input: "3[a2[c]]" Output: "accaccacc"
Test cases
Case 1
Input: "3[a]2[bc]" Expected: "aaabcbc"
Case 2
Input: "3[a2[c]]" Expected: "accaccacc"
Case 3
Input: "2[abc]3[cd]ef" Expected: "abcabccdcdcdef"
Case 4
Input: "10[a]" Expected: "aaaaaaaaaa"
View solutionHide solution1 approach
1. Stack of (previous string, repeat count)
Time O(output length)Space O(output length)
On "[" save the current string and number and start fresh; on "]" pop and append the current string repeated.
function decodeString(s) { const st = []; let cur = '', num = 0; for (const c of s) { if (c >= '0' && c <= '9') num = num * 10 + Number(c); else if (c === '[') { st.push([cur, num]); cur = ''; num = 0; } else if (c === ']') { const [prev, k] = st.pop(); cur = prev + cur.repeat(k); } else cur += c; } return cur;}