Keshawn_lu's Blog

Leetcode 1048. 最长字符串链

动态规划
字数统计: 485阅读时长: 2 min
2023/04/27 Share

题目简介：

给出一个单词数组 words ，其中每个单词都由小写英文字母组成。

如果我们可以 不改变其他字符的顺序 ，在 wordA 的任何地方添加 恰好一个 字母使其变成 wordB ，那么我们认为 wordA 是 wordB 的 前身 。

  • 例如，"abc" 是 "abac" 的 前身 ，而 "cba" 不是 "bcad" 的 前身

词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，其中 word1 是 word2 的前身，word2 是 word3 的前身，依此类推。一个单词通常是 k == 1 的 单词链 。

从给定单词列表 words 中选择单词组成词链，返回 词链的 最长可能长度 。

示例 1：

1
2
3
输入：words = ["a","b","ba","bca","bda","bdca"]
输出：4
解释：最长单词链之一为 ["a","ba","bda","bdca"]

提示：

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 16
  • words[i] 仅由小写英文字母组成。

思路：

首先对数组进行长度从小到大的排序。

然后依次遍历数组，对于每一个word，我们尝试去掉它的任意一个字符，观察去掉后的字符串是否之前在哈希表中出现过，若出现过，则说明这是它的前身，我们更新map[words[i]] = max(map[words[i]], map[pre_s] + 1)。

同时，在遍历中维护词链的最大值即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:

    int longestStrChain(vector<string>& words) {

        unordered_map<string, int> map;

        sort(words.begin(), words.end(), [&](string& a, string& b){

            return a.size() < b.size();
        });

        int res = 0;
        for(int i = 0; i < words.size(); ++i){

            map[words[i]] = 1;

            for(int j = 0; j < words[i].size(); ++j){

                //尝试去掉每个字符
                string pre_s = words[i].substr(0, j) + words[i].substr(j + 1);

                if(map.count(pre_s))    //找到了前身
                    map[words[i]] = max(map[words[i]], map[pre_s] + 1);
            }

            res = max(res, map[words[i]]);
        }

        return res;
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网