Как сделать проверку на корректную вложенность в скобки ((([])){})?

Question

[MishaXXL]

Правильным ответом будут все корректно вложенные или закрытые поочередно скобки

const str = "()[]{}" // true
const str2 = "{[()]}" // true
const str3 = "({{{{}}}))" // false
const str4 = "((([])){})" // true

У меня получилось решить все, кроме const str4 = "((([])){})"
Как выполнить поиск по такому типу конструкции?
Из вариантов пришло в голову рекурсивно сделать через replaceпо кругу пуская варианты (), [], {}, но мне кажется это кринжовое решение

Текущее решение писалось по мере добавления непройденных кейсов и добавление их обработки
https://playcode.io/1851223

Сама задача
https://leetcode.com/problems/valid-parentheses/su...

Comments

[godsplane]

прочитай про стеки, да и на самом литкоде есть решение этой задачи с подробностями.
так же тут отличное объяснение https://ru.stackoverflow.com/questions/548186/%D0%...

[Rsa97]

MishaXXL, Стек или, как его ещё называют, магазин - это структура LIFO (Last In First Out). Можно представить как столбик монет, где новую монету можно положить только наверх (на вершину стека) и снять тоже только сверху (с вершины стека). Класть/доставать монеты из середины или снизу в классическом стеке нельзя.
И да, стек вызова - это тоже классический стек.

Answer 1

[Владимир Римидалв]

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    //hash function for partheses
    let map = { "}": "{", "]": "[", ")": "(" };
    let temp = [];



    //Iterates
    for(i in s){
        //if a index that matches a closing bracket - continue
        if(s[i] in map){
            //if the temp isn't empty, and the top of the stack is that closing bracket - pop it
            if(temp.length > 0 && temp[temp.length-1] === map[s[i]]){
                temp.pop();
            }
            //else we break it - return false
            else{
                return false;
            }
        }
        //else we push the opening bracket onto the stack
        else{
            temp.push(s[i]);
        }
    }
    //else we return true if the temp is empty
    return temp.length === 0;
};

Прямо в литкоде есть решения, можно открыть Solutions, отфильтровать по языку и читать с описанием, можно перейти к all submissions и выбрать самое быстрое решение.

Comments

[MishaXXL]

Спасибо, обычно на кодварсе сидел, там пока не решишь, нельзя посмотреть )

[Алексей 〒.]

MishaXXL, именно зачтенные решения так же можно посмотреть только после прохождения всех тестов.
Те что видны до решения это пользователи в обсуждениях свои варианты публикуют, ну и Решения с объяснениями в LeetCode Premium

[MishaXXL]

Алексей 〒., а как решать задачи, которые выдают неадекватные ошибки?

Например эта
https://leetcode.com/problems/merge-k-sorted-lists/

Дано [[1,4,5],[1,3,4],[2,6]]
Нужно получить [1,1,2,3,4,4,5,6]

Тип результата ListNode
А сам этот тип какая-то шляпа, а не массив с числами

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

Может я что-то не понимаю, но вот банальный пример в лоб

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    if(!lists.length) return null
    return [1,1,2,3,4,4,5,6]
}

Выдает ошибку

Line 15: Char 5: error TS2739: Type 'number[]' is missing the following properties from type 'ListNode': val, next

Как мне вернуть массив чисел в результат, если мне нельзя вернуть массив чисел?

[Алексей 〒.]

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.

Входные данные: массив связных список, выходные: связный список. Логично, что ругается на возвращаемый тип, когда вы пытаетесь вернуть массив.
Вот пример связного списка с первыми элементом из каждого списка:

return new ListNode(lists[0].val, new ListNode(lists[1].val, new ListNode(lists[2].val, null));

По хорошему прежде чем приступать к заданию надо ознакомиться с используемыми структурами данных в нем.

[dim5x]

MishaXXL, потому что это задача на связные списки?
А вы пытаетесь сдать простой массив, не имеющий нужных атрибутов.