Привет! Давайте погрузимся в другую проблему алгоритма. Сегодняшняя проблема исходит от Leetcode's Top Interview Questions - Easy в главе Другое.

В действительных скобках:

Учитывая строку s, содержащую только символы '(', ')', '{', '}', '[' и ']', определите, является ли входная строка допустимой.

Строка ввода допустима, если:

Открытые скобки должны закрываться скобками того же типа.

Открытые скобки должны быть закрыты в правильном порядке.

Примеры:

Input: s = "()"
Output: true
Input: s = "()[]{}"
Output: true
Input: s = "(]"
Output: false
Input: s = "([)]"
Output: false
Input: s = "{[]}"
Output: true

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

Я знал, что мне нужно будет перебирать входную строку, поэтому я пошел дальше и настроил начальный цикл.

for (let i = 0; i < s.length; i++) {
// do something here with s[i]
}

Теперь я хочу иметь возможность сравнить текущий строковый символ, на котором я нахожусь, чтобы определить правую скобку. Кроме того, поскольку скобки должны быть такими же, когда они открываются и закрываются, мне нужно настроить это соединение. Я могу решить обе проблемы с помощью одной структуры данных. Есть догадки?

…

Если вы сказали Object (или Hash или Dictionary, в зависимости от языка), вы правы! Я создал объект, который назвал картой, где открывающие скобки - это ключи, а значения - закрывающие скобки.

const map = {
        '(': ')',
        '{': '}',
        '[': ']'
}

Теперь, когда я просматриваю входную строку, если я натолкнусь на открывающую скобку, я хочу продолжить просмотр входной строки. Если мне попадается закрывающая скобка, я хочу проверить, соответствует ли открывающая скобка в правильном порядке. Для этого я создал массив, в котором все мои открывающие скобки будут храниться в правильном порядке с помощью методов push () и pop (). Затем, просматривая строку ввода, каждый раз, когда я встречаю открывающую скобку, я могу добавить ее в массив. Когда я сталкиваюсь с закрывающей скобкой (или не открывающей скобкой), я могу взять последнюю открывающую скобку, которую я добавил в массив, и проверить, соответствуют ли они скобкам. Если это так, мы продолжаем просмотр входной строки. Если они не совпадают, значит, у меня недействительные скобки, и я могу вернуть false.

for (let i= 0; i < s.length; i++) {
    if (s[i] in map) {
        k.push(s[i])
    } else {
        let opening = k.pop()
        if (map[opening] !== s[i]) {
            return false
        }
    }
}

Как видите, я перебираю строку. Сначала, используя оператор in, я проверяю, есть ли у меня открывающая скобка. Если я это сделаю, я вставлю открывающую скобку в свой массив. Если нет, то у меня есть закрывающая скобка. Эта закрывающая скобка должна совпадать с последней открывающей скобкой, которую я добавил в свой массив, чтобы считаться правильным порядком. Я использую метод pop (), чтобы захватить последнюю добавленную открывающую скобку. Зная открывающую скобку, я могу получить доступ к значению, связанному с ней в моем объекте, для сравнения с текущей закрывающей скобкой, в которой я сейчас нахожусь во входной строке. Если они не совпадают, я возвращаю false. Если они совпадают, я продолжаю перебирать строку.

Я добавил несколько последних штрихов:

  1. Допустимые скобки всегда означают, что входная строка должна содержать четное количество символов. Если длина строки нечетная, это означает, что у меня будет недействительная открывающая или закрывающая скобка. Поэтому вместо того, чтобы перебирать весь массив и прийти к такому выводу, я могу выполнить эту простую проверку, не выполняя весь метод, и сэкономить много времени.
  2. Если я перебираю всю строку, не возвращая false, тогда у меня должна быть действительная строка, верно? Вы были бы почти правы. Представьте, что входная строка - «{{((«. Поскольку длина четная, метод продолжит выполнение цикла по строке. Цикл никогда не вернет false, потому что все они открывающие скобки, которые выглядят закрыто. Это все еще недопустимая строка. Поэтому в конце, вместо того, чтобы просто вернуть истину после завершения цикла for, я использую условную логику через тернарный оператор, чтобы проверить, пуст ли мой массив. Если array пуст, то это означает, что я правильно сопоставил каждую скобку.Если у меня что-то осталось в массиве, чем у меня нет, поэтому мне нужно вернуть false.

Помня об этом, просмотрите полный код:

var isValid = function(s) {
    if (s.length % 2 !== 0){return false}
    
    let k = []
    
    const map = {
        '(': ')',
        '{': '}',
        '[': ']'
    }
    
    for (let i= 0; i < s.length; i++) {
        if (s[i] in map) {
            k.push(s[i])
        } else {
            let opening = k.pop()
            if (map[opening] !== s[i]) {
                return false
            }
        }
    }
    
    return k.length !== 0 ? false : true
};

Временная сложность этого была бы O (n), потому что я знаю, что мой цикл for будет работать в зависимости от значения input (n). Выполняя это на LeetCode, время выполнения было 83 мс , что лучше, чем 29,44% заявок. Однако, глядя на некоторые другие решения за 50–70 мс (верхние 90%), мой код почти идентичен. Кроме того, я определенно верю, что существует рекурсивный способ завершить это решение, которое может улучшить производительность.

Я определенно хотел бы услышать, как мой код можно было бы улучшить, если бы у вас был другой подход к этой проблеме или как вы подходили к решению этого алгоритма. Если вы боролись с этим, я надеюсь, что это поможет прояснить это!

Следите за новыми решениями LeetCode в будущем!

LeetCode серии:

1. Содержит дубликаты
2. Объединить отсортированный массив
3. Проверка высоты
4. Действительный палиндром
5. Счастливое число
6. Самый длинный общий префикс
7. Подъем по лестнице
8. Допустимые скобки
9. Треугольник Паскаля
10. Максимальный подмассив

Больше контента на plainenglish.io