### 题目描述 **最长字符串链** 给定一个字符串数组 `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 代码示例 ```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 代码示例 ```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 代码示例 ```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数组中的最大值 } ``` ### 码小课 码小课网站中提供了更多关于算法和数据结构的学习内容，包括动态规划、字符串处理、排序算法等，欢迎大家前往学习交流，不断提升自己的编程能力。