Стек и задача с собеседования

В этом уроке ты

Научишься применять стек на практике.
Решишь с помощью стека популярную задачу с собеседования.
Оценишь сложность решения задачи по времени и памяти.

Задача с собеседования

Условие

Дана строка s, которая может содержать символы (, ), {, }, [, ], а также символы латинского алфавита. Необходимо определить, является ли строка s правильной.

Строка считается правильной, если выполняются следующие условия:

Каждой открывающей скобке соответствует закрывающая скобка того же типа.
Скобки закрываются в правильном порядке.
Символы латинского алфавита не влияют на правильность строки.

Пример 1

Ввод: s = "[Hello]({}({}[])())()(World)"
Вывод: true

Пример 2

Ввод: s = "()([})"
Вывод: false
Объяснение: круглую скобку пытается закрыть фигурная скобка, это неправильно.

Пример 3

Ввод: s = "())"
Вывод: false
Объяснение: закрывающих скобок больше, чем открывающих.

Решение задачи

public class Solution
{
    public static bool IsBalanced(string s)
    {
        Stack<char> stack = new Stack<char>();
        Dictionary<char, char> pairs = new Dictionary<char, char>
        {
            { '{', '}' },
            { '(', ')' },
            { '[', ']' }
        };

        foreach (char charElem in s)
        {
            if (charElem != '{' && charElem != '[' && charElem != '(' && 
                charElem != '}' && charElem != ']' && charElem != ')')
            {
                // Пропускаем все латинские символы, потому что они не влияют на результат
                continue;
            }

            if (pairs.ContainsKey(charElem))
            {
                // Если скобка открытая - просто добавляем в стек
                stack.Push(charElem);
                continue;
            }

            // Перед нами закрывающаяся скобка, но стек пуст
            if (stack.Count == 0)
            {
                return false;
            }

            // Удаляем последний элемент из стека
            char lastChar = stack.Pop();

            // Проверяем, что последний элемент в стеке и текущий образуют пару
            // Если пару не образуют, то возвращаем false
            if (pairs[lastChar] != charElem)
            {
                return false;
            }
        }

        // Если стек пуст, значит все скобки сбалансированы
        return stack.Count == 0;
    }
}

#include <stack>
#include <unordered_map>
#include <string>

using namespace std;

bool isBalanced(const string& s) {
    stack<char> stack;
    unordered_map<char, char> pairs = {{'{', '}'}, {'(', ')'}, {'[', ']'}};

    for (char charElem : s) {
        if (charElem != '{' && charElem != '[' && charElem != '(' && charElem != '}' && charElem != ']' && charElem != ')') {
            // Пропускаем все латинские символы, потому что они не влияют на результат
            continue;
        }

        if (pairs.count(charElem)) {
            // если скобка открытая - просто добавляем в стек
            stack.push(charElem);
            continue;
        }

        // перед нами закрывающаяся скобка, но стек пуст
        if (stack.empty()) {
            return false;
        }

        // удаляем последний элемент из стека
        char lastChar = stack.top();
        stack.pop();

        // проверяем, что последний элемент в стеке и текущий образуют пару
        // если пару не образуют, то вернем False
        if (pairs[lastChar] != charElem) {
            return false;
        }
    }
    return stack.empty();
}

#include <stack>
#include <unordered_map>
#include <string>

using namespace std;

bool isBalanced(const string& s) {
    stack<char> stack;
    unordered_map<char, char> pairs = {{'{', '}'}, {'(', ')'}, {'[', ']'}};

    for (char charElem : s) {
        if (charElem != '{' && charElem != '[' && charElem != '(' && charElem != '}' && charElem != ']' && charElem != ')') {
            // Пропускаем все латинские символы, потому что они не влияют на результат
            continue;
        }

        if (pairs.count(charElem)) {
            // если скобка открытая - просто добавляем в стек
            stack.push(charElem);
            continue;
        }

        // перед нами закрывающаяся скобка, но стек пуст
        if (stack.empty()) {
            return false;
        }

        // удаляем последний элемент из стека
        char lastChar = stack.top();
        stack.pop();

        // проверяем, что последний элемент в стеке и текущий образуют пару
        // если пару не образуют, то вернем False
        if (pairs[lastChar] != charElem) {
            return false;
        }
    }
    return stack.empty();
}

package main

func isBalanced(s string) bool {
    stack := []rune{}
    pairs := map[rune]rune{'{': '}', '(': ')', '[': ']'}

    for _, char := range s {
        if char != '{' && char != '[' && char != '(' && char != '}' && char != ']' && char != ')' {
            // Пропускаем все латинские символы, потому что они не влияют на результат
            continue
        }

        if _, exists := pairs[char]; exists {
            // если скобка открытая - просто добавляем в стек
            stack = append(stack, char)
            continue
        }

        // перед нами закрывающаяся скобка, но стек пуст
        if len(stack) == 0 {
            return false
        }

        // удаляем последний элемент из стека
        lastChar := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        // проверяем, что последний элемент в стеке и текущий образуют пару
        // если пару не образуют, то вернем False
        if pairs[lastChar] != char {
            return false
        }
    }
    return len(stack) == 0
}

import java.util.Stack;
import java.util.HashMap;

class Solution {
    public boolean isBalanced(String s) {
        Stack<Character> stack = new Stack<>();
        HashMap<Character, Character> pairs = new HashMap<>();
        pairs.put('{', '}');
        pairs.put('(', ')');
        pairs.put('[', ']');

        for (char charElem : s.toCharArray()) {
            if (charElem != '{' && charElem != '[' && charElem != '(' && charElem != '}' && charElem != ']' && charElem != ')') {
                // Пропускаем все латинские символы, потому что они не влияют на результат
                continue;
            }

            if (pairs.containsKey(charElem)) {
                // если скобка открытая - просто добавляем в стек
                stack.push(charElem);
                continue;
            }

            // перед нами закрывающаяся скобка, но стек пуст
            if (stack.isEmpty()) {
                return false;
            }

            // удаляем последний элемент из стека
            char lastChar = stack.pop();

            // проверяем, что последний элемент в стеке и текущий образуют пару
            // если пару не образуют, то вернем False
            if (pairs.get(lastChar) != charElem) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}

from typing import *

def is_balanced(s: str) -> bool:
    stack = []
    pairs = {'{': '}', '(': ')', '[': ']'}
    for char in s:
        if char not in {'{', '[', '(', '}', ']', ')'}:
            # Пропускаем символы, которые не являются скобками
            continue
        if char in pairs:
            # Добавляем открывающую скобку в стек
            stack.append(char)
            continue
        if len(stack) == 0:
            # Встретили закрывающую скобку, но в стеке
            # нет открывающих – ошибка
            return False
 
        # Удаляем последнюю открывающую скобку из стека
        last_char = stack.pop()
 
        # Проверяем, соответствует ли текущая закрывающая скобка
        # последней открывающей
        if pairs[last_char] != char:
            return False

    # Проверяем, что в стеке не осталось незакрытых открывающих скобок
    return len(stack) == 0

Используем стек, чтобы хранить открывающие скобки и проверять, соответствует ли им каждая закрывающая скобка. Если мы встретим несоответствие или стек окажется не пуст в конце, то строка неправильная.

Сложность работы со стеком

При работе со стеком самая сложная часть — придумать правильные условия, когда добавлять элементы в стек и когда их удалять. Чем больше задач на эту тему ты решишь, тем легче тебе будет находить решения таких задач в будущем.

Чаще всего стек используется:

для проверки правильности последовательности скобок;
когда для формирования ответа нужно использовать предыдущие значения или состояния.

Это не единственные примеры применения стека, но они помогут тебе освоиться на начальном этапе.

Что дальше

Теперь переходи к решению задач, чтобы закрепить новые знания на практике!