Swift | LeetCode

Задача: 394. Decode String
Сложность: medium

Дана закодированная строка, вернуть её декодированную версию.

Правило кодирования следующее: k[закодированная_строка], где закодированная_строка внутри квадратных скобок повторяется ровно k раз. Обратите внимание, что k гарантированно является положительным целым числом.

Можно предположить, что входная строка всегда допустима; нет лишних пробелов, квадратные скобки корректно сформированы и т.д. Более того, можно предположить, что исходные данные не содержат никаких цифр, и что цифры используются только для обозначения количества повторений, k. Например, не будет таких входных данных, как 3a или 2[4].

Тестовые случаи сгенерированы так, что длина выходной строки никогда не превысит 105.

Пример:

Input: s = "3[a]2[bc]"
Output: "aaabcbc"

👨‍💻

Алгоритм:

1⃣Проходите по строке s и обрабатывайте каждый символ. Если текущий символ не является закрывающей скобкой ], поместите его в стек.

2⃣Если текущий символ является закрывающей скобкой ], начните декодировать последнюю пройденную строку. Извлекайте из стека символы, пока следующий символ не станет открывающей скобкой [, и добавляйте каждый символ (a-z) к decodedString. Затем извлеките открывающую скобку [ из стека и извлекайте символы, пока следующий символ является цифрой (0-9), чтобы собрать число k.

3⃣Декодируйте шаблон k[decodedString], помещая decodedString в стек k раз. После того как вся строка будет пройдена, извлеките результат из стека и верните его.

😎

Решение:

class Solution {
    func decodeString(_ s: String) -> String {
        var stack = [Character]()
        
        for char in s {
            if char == "]" {
                var decodedString = ""
                while let last = stack.last, last != "[" {
                    decodedString = String(stack.removeLast()) + decodedString
                }
                stack.removeLast()
                
                var k = 0
                var base = 1
                while let last = stack.last, let digit = last.wholeNumberValue {
                    k += digit * base
                    base *= 10
                    stack.removeLast()
                }
                
                for _ in 0..<k {
                    for c in decodedString {
                        stack.append(c)
                    }
                }
            } else {
                stack.append(char)
            }
        }
        
        return String(stack)
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Please open Telegram to view this post