1048. 最长字符串链

发表于 分类于 阅读次数： Waline： 本文字数： 849 阅读时长 ≈ 3 分钟

考点

  • 线性DP

思路

1. 问题描述

给定一个字符串数组 words，如果字符串 A 可以通过在字符串 B 中删除恰好一个字符得到，则称 A 是 B 的前驱（predecessor）。

一个字符串链是一个序列 \[ w_1 \rightarrow w_2 \rightarrow \cdots \rightarrow w_k \] 满足对任意 \(i\)，都有 \(w_i\) 是 \(w_{i+1}\) 的前驱。

目标：求可以构成的最长字符串链的长度。

2. 问题建模

2.1 关键观察

  1. 若 \(w_i\) 是 \(w_{i+1}\) 的前驱，则必有 \[ |w_{i+1}| = |w_i| + 1 \]

  2. 前驱关系是有向的，且字符串长度严格递增，因此整个问题可以视为：

    • 一个 有向无环图（DAG）
    • 按字符串长度进行 拓扑序 DP

2.2 状态定义

定义动态规划状态： \[ \boxed{ f(w) = \text{以字符串 } w \text{ 作为结尾的最长字符串链长度} } \]

2.3 状态初始化

  • 任意字符串自身都可以构成长度为 1 的链：

\[ f(w) \ge 1 \]

3. 前驱判定的等价转化（核心建模）

与其判断“两个字符串是否只差一个字符”，不如进行如下等价转化：

枚举当前字符串删除一个字符后得到的所有字符串

设当前字符串为 w，长度为 L，则它的所有可能前驱为： \[ \text{prev}_i = w[0..i-1] + w[i+1..L-1], \quad 0 \le i < L \] 若 prev_i 存在于已处理的字符串集合中，则它一定是合法前驱。

4. 状态转移方程

对于任意字符串 \(w\)，其状态转移为： \[ \boxed{ f(w) = \max \left( 1,\ \max_{\substack{w' \text{ 是 } w \text{ 的前驱}}} \left( f(w') + 1 \right) \right) } \] 对应实现中：

  • 枚举删除位置 \(i\)
  • 得到前驱字符串 pre
  • 若 pre 在哈希表中，则尝试更新

5. 计算顺序（拓扑序）

为了保证在计算 \(f(w)\) 时，其所有前驱已经被计算完成：

  • 按字符串长度从小到大排序
  • 依次进行 DP

这是 DAG 上的标准拓扑序 DP。

6. 复杂度分析

设：

  • 字符串数量为 \(n\)
  • 最大字符串长度为 \(L\)

时间复杂度

  • 对每个字符串枚举 \(L\) 个删除位置
  • 每次构造字符串复杂度 \(O(L)\)

\[ \boxed{O(n \cdot L^2)} \]

空间复杂度

  • 哈希表存储 DP 值

\[ \boxed{O(n \cdot L)} \]

7. 算法正确性说明（简要）

  • 每个状态 \(f(w)\) 只依赖于长度更短的字符串
  • 所有合法前驱均通过“删除一个字符”被枚举
  • 拓扑序保证无后效性

因此该 DP 能正确计算最长字符串链。

8. AC代码

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    // 自定义比较器：按字符串长度升序排序
    struct cmp {
        bool operator()(string& x, string& y) {
            return x.size() < y.size();
        }
    };

    int longestStrChain(vector<string>& words) {
        int n = words.size();
        int res = 0;

        // 按长度排序，保证 DP 按拓扑序进行
        sort(words.begin(), words.end(), cmp());

        // f[w]：以字符串 w 结尾的最长字符串链长度
        unordered_map<string, int> f;

        for (string& x : words) {
            // 至少可以单独成链，长度为 1
            int mx = max(f[x], 1);

            // 枚举删除 x 的第 i 个字符
            for (int i = 0; i < x.size(); ++i) {
                // 构造前驱字符串
                string pre = x.substr(0, i) + x.substr(i + 1);

                // 如果该前驱已经出现过
                auto it = f.find(pre);
                if (it != f.end()) {
                    // 状态转移：接在前驱链后
                    mx = max(mx, it->second + 1);
                }
            }

            // 更新 DP 值
            f[x] = mx;

            // 更新全局答案
            res = max(res, mx);
        }

        return res;
    }
};