Задача: 1048. Longest String Chain
Сложность: easy

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

Например, "abc" является предшественником "abac", а "cba" не является предшественником "bcad". Цепочка слов - это последовательность слов [word1, word2, ..., wordk] с k >= 1, где word1 является предшественником word2, word2 является предшественником word3 и так далее. Одиночное слово тривиально является цепочкой слов с k == 1. Верните длину самой длинной возможной цепочки слов со словами, выбранными из заданного списка слов.

Пример:

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4

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

1⃣Отсортируй список слов по длине.

2⃣Используй динамическое программирование для вычисления длины самой длинной цепочки для каждого слова.

3⃣Верни максимальную длину среди всех цепочек.

😎 Решение:

function longestStrChain(words) {
    words.sort((a, b) => a.length - b.length);
    let dp = new Map();
    let longestChain = 1;
    
    for (let word of words) {
        dp.set(word, 1);
        for (let i = 0; i < word.length; i++) {
            let predecessor = word.slice(0, i) + word.slice(i + 1);
            if (dp.has(predecessor)) {
                dp.set(word, Math.max(dp.get(word), dp.get(predecessor) + 1));
            }
        }
        longestChain = Math.max(longestChain, dp.get(word));
    }
    
    return longestChain;
}

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