Algorithm
Problem Name: 394. Decode String
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].
The test cases are generated so that the length of the output will never exceed 105.
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"
Constraints:
1 <= s.length <= 30sconsists of lowercase English letters, digits, and square brackets'[]'.sis guaranteed to be a valid input.- All the integers in
sare in the range[1, 300].
Code Examples
#1 Code Example with C Programming
Code -
C Programming
struct node {
char *leading_string;
int leading_len;
int repeat;
};
char* decodeString(char* s) {
struct node stack[100], *p;
int sp = 0;
int n;
char *buff;
int sz, len;
char *newbuff = NULL;
int newsz, newlen;
buff = NULL;
sz = len = 0;
n = 0;
while (*s) {
if (*s == '[') {
p = &stack[sp ++]; // push and save
p->leading_string = buff;
p->leading_len = len;
buff = NULL;
sz = len = 0;
p->repeat = n;
n = 0;
} else if (*s == ']') {
p = &stack[-- sp]; // pop and expand
newlen = p->leading_len + p->repeat * len;
newsz = newlen + 10;
newbuff = realloc(p->leading_string, newsz * sizeof(char));
//assert(newbuff);
if (!p->leading_string) {
newbuff[0] = 0;
}
while (p->repeat) {
strcat(newbuff, buff);
p->repeat --;
}
free(buff);
sz = newsz;
len = newlen;
buff = newbuff;
} else if (*s >= '0' && *s < = '9') {
n = n * 10 + (*s) - '0';
} else {
if (len + 1 >= sz) {
if (sz == 0) sz = 10;
else sz *= 2;
buff = realloc(buff, sz * sizeof(char));
//assert(buff);
}
buff[len ++] = *s;
buff[len] = 0; // null terminated
}
s ++;
}
if (!buff) buff = calloc(1, sizeof(char));
//assert(buff);
return buff;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
string decodeString(string s) {
if(s.empty()) return "";
string res = "";
int i = 0, j = 0;
while(j < s.size()){
while(j < s.size() && isalpha(s[j])) j++;
res += s.substr(i, j - i);
i = j;
if(j == s.size()) break;
while(isdigit(s[j])) j++;
int k = stoi(s.substr(i, j - i));
int cnt = 1;
i = j + 1;
while(cnt != 0)
if(s[++j] == ']') cnt--;
else if(s[j] == '[') cnt++;
while(k--) res += decodeString(s.substr(i, j - i)>;
i = ++j;
}
return res;
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public String decodeString(String s) {
Stack stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == ']') {
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty() && stack.peek() != '[') {
sb.append(stack.pop());
}
stack.pop();
String temp = sb.toString();
sb.setLength(0);
while (!stack.isEmpty() && Character.isDigit(stack.peek())) {
sb.append(stack.pop());
}
int count = Integer.parseInt(sb.reverse().toString());
while (count-- > 0) {
for (int i = temp.length() - 1; i >= 0; i--) {
stack.push(temp.charAt(i));
}
}
} else {
stack.push(c);
}
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.reverse().toString();
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const decodeString = function(s) {
const repeated = [];
const sbStack = [];
let mul = 0;
let sb = "";
for (let i = 0; i < s.length; i++) {
const c = s.charAt(i);
if (isDigit(c)) {
if (mul === 0) sbStack.push(sb); // here is the trick
mul = mul * 10 + +c;
} else if (c === "[") {
repeated.push(mul);
mul = 0;
sb = "";
} else if (isLetter(c)) {
sb += c;
} else if (c === "]") {
let top = sbStack.pop();
let r = repeated.pop();
while (r-- > 0) top += sb;
sb = top;
}
}
return sb;
};
function isDigit(c) {
return c.charCodeAt(0) >= 48 && c.charCodeAt(0) < = 57;
}
function isLetter(c) {
return (
(c.charCodeAt(0) >= 65 && c.charCodeAt(0) <= 90) ||
(c.charCodeAt(0) >= 97 && c.charCodeAt(0) <= 122)
);
}
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def decodeString(self, s):
stack, num, string = [], 0, ""
for c in s:
if c == "[":
stack += string,
stack += num,
num, string = 0, ""
elif c == "]":
pre_num, pre_string = stack.pop(), stack.pop()
string = pre_string + pre_num * string
elif c.isdigit(): num = num * 10 + int(c)
else: string += c
return string
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
using System.Text;
namespace LeetCode
{
public class _0394_DecodeString
{
public string DecodeString(string s)
{
var countStack = new Stack < int>();
var strStack = new Stack();
var sb = new StringBuilder();
var num = 0;
foreach (var ch in s)
{
if (char.IsDigit(ch))
num = num * 10 + ch - '0';
else if (ch == '[')
{
strStack.Push(sb.ToString());
countStack.Push(num);
sb.Clear();
num = 0;
}
else if (ch == ']')
{
var str = sb.ToString();
sb.Clear();
sb.Append(strStack.Pop());
var count = countStack.Pop();
for (int i = 0; i < count; i++)
sb.Append(str);
}
else
sb.Append(ch);
}
return sb.ToString();
}
}
}
Input
Output