Задача: 288. Unique Word Abbreviation
Сложность: medium

Сокращение слова — это объединение его первой буквы, количества символов между первой и последней буквой и последней буквы. Если слово состоит только из двух символов, то оно является сокращением само по себе.
Например:
dog --> d1g, потому что между первой буквой 'd' и последней буквой 'g' одна буква.
internationalization --> i18n, потому что между первой буквой 'i' и последней буквой 'n' 18 букв.
it --> it, потому что любое слово из двух символов является своим собственным сокращением.
Реализуйте класс ValidWordAbbr:
ValidWordAbbr(String[] dictionary) Инициализирует объект со словарем слов.
boolean isUnique(string word) Возвращает true, если выполняется одно из следующих условий (в противном случае возвращает false):
В словаре нет слова, сокращение которого равно сокращению слова word.
Для любого слова в словаре, сокращение которого равно сокращению слова word, это слово и word одинаковы.

Пример:

Input
["ValidWordAbbr", "isUnique", "isUnique", "isUnique", "isUnique", "isUnique"]
[[["deer", "door", "cake", "card"]], ["dear"], ["cart"], ["cane"], ["make"], ["cake"]]
Output
[null, false, true, false, true, true]

Explanation
ValidWordAbbr validWordAbbr = new ValidWordAbbr(["deer", "door", "cake", "card"]);
validWordAbbr.isUnique("dear"); // return false, dictionary word "deer" and word "dear" have the same abbreviation "d2r" but are not the same.
validWordAbbr.isUnique("cart"); // return true, no words in the dictionary have the abbreviation "c2t".
validWordAbbr.isUnique("cane"); // return false, dictionary word "cake" and word "cane" have the same abbreviation  "c2e" but are not the same.
validWordAbbr.isUnique("make"); // return true, no words in the dictionary have the abbreviation "m2e".
validWordAbbr.isUnique("cake"); // return true, because "cake" is already in the dictionary and no other word in the dictionary has "c2e" abbreviation.

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

1⃣Инициализация:
Создайте словарь сокращений abbrDict, который будет хранить сокращения слов в виде ключей и булевы значения, указывающие, уникально ли сокращение.
Создайте множество dict, содержащее все слова из словаря, чтобы быстро проверять наличие слова в словаре.

2⃣Генерация сокращений:
При инициализации объекта ValidWordAbbr пройдите через каждое слово в словаре и создайте его сокращение.
Если сокращение уже существует в abbrDict, установите значение в false (не уникальное). В противном случае установите значение в true (уникальное).

3⃣Проверка уникальности:
Для метода isUnique создайте сокращение для входного слова и проверьте, есть ли это сокращение в abbrDict.
Если сокращение отсутствует в abbrDict, возвращайте true.
Если сокращение присутствует и оно уникально, проверьте, есть ли это слово в словаре. Если да, возвращайте true, в противном случае - false.

😎 Решение:

class ValidWordAbbr {
    constructor(dictionary) {
        this.abbrDict = new Map();
        this.dict = new Set(dictionary);
        for (const word of this.dict) {
            const abbr = this.toAbbr(word);
            this.abbrDict.set(abbr, !this.abbrDict.get(abbr));
        }
    }

    isUnique(word) {
        const abbr = this.toAbbr(word);
        const hasAbbr = this.abbrDict.get(abbr);
        return hasAbbr === undefined || (hasAbbr && this.dict.has(word));
    }

    toAbbr(word) {
        const n = word.length;
        if (n <= 2) {
            return word;
        }
        return `${word[0]}${n - 2}${word[n - 1]}`;
    }
}

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

Задача: 323. Number of Connected Components in an Undirected Graph
Сложность: medium

У вас есть граф из n узлов. Вам дано целое число n и массив edges, где edges[i] = [ai, bi] указывает на наличие ребра между ai и bi в графе.
Верните количество связных компонентов в графе.

Пример:

Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2

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

1⃣Создание списка смежности
Создайте список смежности, такой что adj[v] содержит все смежные вершины вершины v.

2⃣Инициализация посещенных узлов
Инициализируйте хэш-карту или массив visited для отслеживания посещенных вершин.

3⃣Подсчет компонентов
Определите счетчик и инициализируйте его нулем. Итерируйте по каждой вершине в edges, и если вершина еще не была посещена, начните DFS с этой вершины. Добавляйте каждую вершину, посещенную во время DFS, в visited. Каждый раз, когда начинается новый DFS, увеличивайте счетчик на один. В конце, счетчик будет содержать количество связных компонентов в неориентированном графе.

😎 Решение:

function countComponents(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    edges.forEach(([u, v]) => {
        adj[u].push(v);
        adj[v].push(u);
    });

    const visited = new Set();
    let count = 0;

    const dfs = (node) => {
        const stack = [node];
        while (stack.length > 0) {
            const current = stack.pop();
            if (!visited.has(current)) {
                visited.add(current);
                adj[current].forEach(neighbor => {
                    if (!visited.has(neighbor)) stack.push(neighbor);
                });
            }
        }
    };

    for (let i = 0; i < n; i++) {
        if (!visited.has(i)) {
            dfs(i);
            count++;
        }
    }

    return count;
}

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

Задача: 106. Construct Binary Tree from Inorder and Postorder Traversal
Сложность: medium

Даны два массива целых чисел: inorder и postorder, где inorder — это массив обхода в глубину бинарного дерева слева направо, а postorder — это массив обхода в глубину после обработки всех потомков узла. Постройте и верните соответствующее бинарное дерево.

Пример:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

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

1️⃣Создайте хэш-таблицу (hashmap) для хранения соответствия значений и их индексов в массиве обхода inorder.

2️⃣Определите вспомогательную функцию helper, которая принимает границы левой и правой части текущего поддерева в массиве inorder. Эти границы используются для проверки, пусто ли поддерево. Если левая граница больше правой (in_left > in_right), то поддерево пустое и функция возвращает None.

3️⃣Выберите последний элемент в массиве обхода postorder в качестве корня. Значение корня имеет индекс index в обходе inorder. Элементы от in_left до index - 1 принадлежат левому поддереву, а элементы от index + 1 до in_right — правому поддереву. Согласно логике обхода postorder, сначала рекурсивно строится правое поддерево helper(index + 1, in_right), а затем левое поддерево helper(in_left, index - 1). Возвращается корень.

😎 Решение:

var buildTree = function (inorder, postorder) {
    var idx_map = {};
    var post_idx = postorder.length - 1;
    var helper = function (in_left, in_right) {
        if (in_left > in_right) return null;
        var root_val = postorder[post_idx];
        var root = new TreeNode(root_val);
        var index = idx_map[root_val];
        post_idx--;
        root.right = helper(index + 1, in_right);
        root.left = helper(in_left, index - 1);
        return root;
    };
    for (var i = 0; i < inorder.length; i++) idx_map[inorder[i]] = i;
    return helper(0, inorder.length - 1);
};

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