Дана закодированная строка, вернуть её декодированную версию.
Правило кодирования следующее: k[закодированная_строка], где закодированная_строка внутри квадратных скобок повторяется ровно k раз. Обратите внимание, что k гарантированно является положительным целым числом.
Можно предположить, что входная строка всегда допустима; нет лишних пробелов, квадратные скобки корректно сформированы и т.д. Более того, можно предположить, что исходные данные не содержат никаких цифр, и что цифры используются только для обозначения количества повторений, k. Например, не будет таких входных данных, как 3a или 2[4].
Тестовые случаи сгенерированы так, что длина выходной строки никогда не превысит 105.
Пример:
Input: s = "3[a]2[bc]"
Output: "aaabcbc"
C# решение
сопоставлено/оригиналpublic class Solution {
public string DecodeString(string s) {
Stack<char> stack = new Stack<char>();
for (int i = 0; i < s.Length; i++) {
if (s[i] == ']') {
string decodedString = "";
while (stack.Peek() != '[') {
decodedString = stack.Pop() + decodedString;
}
stack.Pop();
int baseValue = 1;
int k = 0;
while (stack.Count > 0 && char.IsDigit(stack.Peek())) {
k = k + (stack.Pop() - '0') * baseValue;
baseValue *= 10;
}
while (k != 0) {
for (int j = decodedString.Length - 1; j >= 0; j--) {
stack.Push(decodedString[j]);
}
k--;
}
} else {
stack.Push(s[i]);
}
}
string result = "";
while (stack.Count > 0) {
result = stack.Pop() + result;
}
return result;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public string DecodeString(string s) {
stack<char> stack = new stack<char>();
for (int i = 0; i < s.size(); i++) {
if (s[i] == ']') {
string decodedString = "";
while (stack.Peek() != '[') {
decodedString = stack.pop() + decodedString;
}
stack.pop();
int baseValue = 1;
int k = 0;
while (stack.size() > 0 && char.IsDigit(stack.Peek())) {
k = k + (stack.pop() - '0') * baseValue;
baseValue *= 10;
}
while (k != 0) {
for (int j = decodedString.size() - 1; j >= 0; j--) {
stack.push(decodedString[j]);
}
k--;
}
} else {
stack.push(s[i]);
}
}
string result = "";
while (stack.size() > 0) {
result = stack.pop() + result;
}
return result;
}
}Java решение
сопоставлено/оригиналclass Solution {
public String decodeString(String s) {
Stack<Character> stack = new Stack<>();
for (char ch : s.toCharArray()) {
if (ch == ']') {
StringBuilder decodedString = new StringBuilder();
while (stack.peek() != '[') {
decodedString.insert(0, stack.pop());
}
stack.pop();
int k = 0;
int base = 1;
while (!stack.isEmpty() && Character.isDigit(stack.peek())) {
k = k + (stack.pop() - '0') * base;
base *= 10;
}
for (int i = 0; i < k; i++) {
for (char c : decodedString.toString().toCharArray()) {
stack.push(c);
}
}
} else {
stack.push(ch);
}
}
StringBuilder result = new StringBuilder();
for (char ch : stack) {
result.append(ch);
}
return result.toString();
}
}JavaScript решение
сопоставлено/оригиналvar decodeString = function(s) {
let stack = [];
for (let i = 0; i < s.length; i++) {
if (s[i] === ']') {
let decodedString = '';
while (stack[stack.length - 1] !== '[') {
decodedString = stack.pop() + decodedString;
}
stack.pop();
let base = 1;
let k = 0;
while (stack.length > 0 && !isNaN(stack[stack.length - 1])) {
k = k + stack.pop() * base;
base *= 10;
}
while (k > 0) {
for (let j = 0; j < decodedString.length; j++) {
stack.push(decodedString[j]);
}
k--;
}
} else {
stack.push(s[i]);
}
}
return stack.join('');
};
console.log(decodeString("3[a2[c]]")); // Output: "accaccacc"Python решение
сопоставлено/оригиналclass Solution:
def decodeString(self, s: str) -> str:
stack = []
for char in s:
if char != ']':
stack.append(char)
else:
decoded_string = ''
while stack[-1] != '[':
decoded_string = stack.pop() + decoded_string
stack.pop()
k = 0
base = 1
while stack and stack[-1].isdigit():
k = k + int(stack.pop()) * base
base *= 10
stack.append(decoded_string * k)
return ''.join(stack)Go решение
сопоставлено/оригиналpackage main
import (
"fmt"
"unicode"
)
func decodeString(s string) string {
stack := []rune{}
for _, char := range s {
if char == ']' {
decodedString := ""
for stack[len(stack)-1] != '[' {
decodedString = string(stack[len(stack)-1]) + decodedString
stack = stack[:len(stack)-1]
}
stack = stack[:len(stack)-1]
base := 1
k := 0
for len(stack) > 0 && unicode.IsDigit(stack[len(stack)-1]) {
k = k + int(stack[len(stack)-1]-'0')*base
stack = stack[:len(stack)-1]
base *= 10
}
for k > 0 {
for j := 0; j < len(decodedString); j++ {
stack = append(stack, rune(decodedString[j]))
}
k--
}
} else {
stack = append(stack, char)
}
}
return string(stack)
}
func main() {
fmt.Println(decodeString("3[a2[c]]")) // Output: "accaccacc"
}Algorithm
Проходите по строке s и обрабатывайте каждый символ. Если текущий символ не является закрывающей скобкой ], поместите его в стек.
Если текущий символ является закрывающей скобкой ], начните декодировать последнюю пройденную строку. Извлекайте из стека символы, пока следующий символ не станет открывающей скобкой [, и добавляйте каждый символ (a-z) к decodedString. Затем извлеките открывающую скобку [ из стека и извлекайте символы, пока следующий символ является цифрой (0-9), чтобы собрать число k.
Декодируйте шаблон k[decodedString], помещая decodedString в стек k раз. После того как вся строка будет пройдена, извлеките результат из стека и верните его.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.