Задача: 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) {
    usort($words, function($a, $b) {
        return strlen($a) - strlen($b);
    });
    
    $dp = [];
    $longestChain = 1;
    
    foreach ($words as $word) {
        $dp[$word] = 1;
        for ($i = 0; $i < strlen($word); $i++) {
            $predecessor = substr($word, 0, $i) . substr($word, $i + 1);
            if (isset($dp[$predecessor])) {
                $dp[$word] = max($dp[$word], $dp[$predecessor] + 1);
            }
        }
        $longestChain = max($longestChain, $dp[$word]);
    }
    
    return $longestChain;
}

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