Задача: 591. Tag Validator
Сложность: hard

Дана строка, представляющая фрагмент кода, реализуйте валидатор тегов для разбора кода и определения его корректности.
Фрагмент кода считается корректным, если соблюдаются все следующие правила:
Код должен быть заключен в корректный закрытый тег. В противном случае код некорректен.
Закрытый тег (не обязательно корректный) имеет точно следующий формат: <TAG_NAME>TAG_CONTENT</TAG_NAME>. Среди них <TAG_NAME> — это начальный тег, а </TAG_NAME> — конечный тег. TAG_NAME в начальном и конечном тегах должен быть одинаковым. Закрытый тег корректен, если и только если TAG_NAME и TAG_CONTENT корректны.
Корректное TAG_NAME содержит только заглавные буквы и имеет длину в диапазоне [1, 9]. В противном случае TAG_NAME некорректен.
Корректное TAG_CONTENT может содержать другие корректные закрытые теги, cdata и любые символы (см. примечание 1), КРОМЕ неподходящих <, неподходящих начальных и конечных тегов, и неподходящих или закрытых тегов с некорректным TAG_NAME. В противном случае TAG_CONTENT некорректен.
Начальный тег неподходящий, если нет конечного тега с тем же TAG_NAME, и наоборот. Однако нужно также учитывать проблему несбалансированных тегов, когда они вложены.
< неподходящий, если не удается найти последующий >. И когда вы находите < или </, все последующие символы до следующего > должны быть разобраны как TAG_NAME (не обязательно корректный).
cdata имеет следующий формат: <![CDATA[CDATA_CONTENT]]>. Диапазон CDATA_CONTENT определяется как символы между <![CDATA[ и первым последующим ]]>.
CDATA_CONTENT может содержать любые символы. Функция cdata заключается в том, чтобы запретить валидатору разбирать CDATA_CONTENT, поэтому даже если в нем есть символы, которые могут быть разобраны как тег (корректный или некорректный), вы должны рассматривать их как обычные символы.

Пример:

Input: code = "<DIV>This is the first line <![CDATA[<div>]]></DIV>"
Output: true

👨‍💻 Алгоритм:

1⃣Инициализируйте стек для отслеживания открытых тегов и флаг для определения наличия тегов. Используйте регулярное выражение для проверки корректности TAG_NAME, TAG_CONTENT и CDATA.

2⃣Пройдитесь по строке, проверяя каждый символ. Если встретите <, определите тип тега (начальный, конечный или CDATA). Обновите стек и индексы в зависимости от найденного типа.

3⃣В конце проверьте, что стек пуст (все теги корректно закрыты) и верните результат.

😎 Решение:

class Solution {
    constructor() {
        this.stack = [];
        this.containsTag = false;
    }

    isValidTagName(s, ending) {
        if (ending) {
            if (this.stack.length > 0 && this.stack[this.stack.length - 1] === s) {
                this.stack.pop();
            } else {
                return false;
            }
        } else {
            this.containsTag = true;
            this.stack.push(s);
        }
        return true;
    }

    isValid(code) {
        const regex = /<[A-Z]{0,9}>([^<]*(<((\/?[A-Z]{1,9}>)|(!\[CDATA\[.*?\]\]>)))?)*/;
        if (!regex.test(code)) {
            return false;
        }

        for (let i = 0; i < code.length; i++) {
            let ending = false;
            if (this.stack.length === 0 && this.containsTag) {
                return false;
            }
            if (code[i] === '<') {
                if (code[i + 1] === '!') {
                    i = code.indexOf("]]>", i + 1);
                    if (i === -1) {
                        return false;
                    }
                    continue;
                }
                if (code[i + 1] === '/') {
                    i++;
                    ending = true;
                }
                const closeIndex = code.indexOf('>', i + 1);
                if (closeIndex === -1 || !this.isValidTagName(code.slice(i + 1, closeIndex), ending)) {
                    return false;
                }
                i = closeIndex;
            }
        }
        return this.stack.length === 0;
    }
}

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

Задача: 336. Palindrome Pairs
Сложность: hard

Вам дан массив уникальных строк words, индексируемый с 0.
Пара палиндромов — это пара целых чисел (i, j), таких что:
0 <= i, j < words.length,
i != j, и
words[i] + words[j] (конкатенация двух строк) является палиндромом.
Верните массив всех пар палиндромов из слов.
Вы должны написать алгоритм с временной сложностью O(сумма длин всех слов в words).

Пример:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]

👨‍💻 Алгоритм:

1⃣Инициализация и подготовка данных:
Создайте структуру для хранения результатов (список пар индексов).
Создайте словарь для хранения слов и их индексов, чтобы ускорить поиск.

2⃣Итерация по всем парам слов и проверка:
Пройдите по всем парам слов в массиве words, используя два вложенных цикла.
Для каждой пары слов проверяйте, образуют ли они палиндром при конкатенации. Это делается путем объединения строк и проверки, равна ли объединенная строка своей обратной версии.

3⃣Добавление найденных пар в результат:
Если проверка на палиндром проходит, добавьте текущую пару индексов в список результатов.
Верните итоговый список всех найденных пар.

😎 Решение:

var palindromePairs = function(words) {
    let pairs = [];
    
    for (let i = 0; i < words.length; i++) {
        for (let j = 0; j < words.length; j++) {
            if (i === j) continue;
            let combined = words[i] + words[j];
            if (combined === combined.split('').reverse().join('')) {
                pairs.push([i, j]);
            }
        }
    }
    
    return pairs;
};

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