题目描述

最长字符串链

给定一个字符串数组 words，每个字符串可以由小写英文字母组成。现在我们要找到一条最长的字符串链，其中每个字符串都是前一个字符串的一个子串（后缀），并且字符串链中字符串的顺序是按照字符串的长度递增的（即，字符串链中 s[i] 的长度必须小于 s[i+1] 的长度）。请返回这条最长字符串链的长度。

示例 1:

输入: ["a","b","ba","bca","bda","bdca"]
输出: 4
解释: 最长字符串链为 "a", "ba", "bda", "bdca"。

示例 2:

输入: ["xbc","pcxbcf","xb","cxbc","pcxbc"]
输出: 5
解释: 可能的最长字符串链为 "xb", "xbc", "cxbc", "pcxbc", "pcxbcf"。

解题思路

这个问题可以使用动态规划（DP）的方法来解决。我们可以定义一个数组 dp，其中 dp[i] 表示以 words[i] 结尾的最长字符串链的长度。对于每个字符串 words[i]，我们遍历它之前的所有字符串 words[j]（j < i），检查 words[j] 是否是 words[i] 的子串，并更新 dp[i] 为 max(dp[i], dp[j] + 1)（如果 words[j] 是 words[i] 的子串）。最后，我们遍历 dp 数组找到其中的最大值，即为所求的最长字符串链的长度。

PHP 代码示例

function longestStrChain($words) {
    usort($words, function($a, $b) {
        return strlen($a) - strlen($b); // 按字符串长度排序
    });

    $n = count($words);
    $dp = array_fill(0, $n, 1); // 初始化dp数组，每个字符串至少可以构成长度为1的链

    for ($i = 0; $i < $n; $i++) {
        for ($j = 0; $j < $i; $j++) {
            if (strpos($words[$i], $words[$j]) !== false) { // 检查是否是子串
                $dp[$i] = max($dp[$i], $dp[$j] + 1);
            }
        }
    }

    return max($dp); // 返回dp数组中的最大值
}

Python 代码示例

def longestStrChain(words):
    words.sort(key=len)  # 按字符串长度排序
    dp = [1] * len(words)  # 初始化dp数组

    for i in range(len(words)):
        for j in range(i):
            if words[j] in words[i]:  # 检查是否是子串
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)  # 返回dp数组中的最大值

JavaScript 代码示例

function longestStrChain(words) {
    words.sort((a, b) => a.length - b.length); // 按字符串长度排序
    const dp = new Array(words.length).fill(1); // 初始化dp数组

    for (let i = 0; i < words.length; i++) {
        for (let j = 0; j < i; j++) {
            if (words[i].startsWith(words[j])) { // 检查是否是子串
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    return Math.max(...dp); // 返回dp数组中的最大值
}

码小课

码小课网站中提供了更多关于算法和数据结构的学习内容，包括动态规划、字符串处理、排序算法等，欢迎大家前往学习交流，不断提升自己的编程能力。