跳转至

1048. 最长字符串链

题目描述

给出一个单词数组 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：

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

示例 2:

输入：words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
输出：5
解释：所有的单词都可以放入单词链 ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

示例 3:

输入：words = ["abcd","dbqca"]
输出：1
解释：字链["abcd"]是最长的字链之一。
["abcd"，"dbqca"]不是一个有效的单词链，因为字母的顺序被改变了。

 

提示：

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

解法

方法一：动态规划

思考

词链要求每次只多一个字符，\(n\le 1000\)、串长 \(\le 16\)，可按长度排序后做序列 DP。以 \(i\) 结尾的最长链，来自某个长度恰少 \(1\) 且为前身的 \(j\)。

双指针判断 \(a\) 能否通过插入一个字符得到 \(b\)。对每个 \(i\) 枚举更短的 \(j\)，满足前身则用 \(f[j]+1\) 更新 \(f[i]\)。

答案为 \(f\) 的最大值。

我们先将 \(\textit{words}\) 按照字符串长度从小到大排序。定义 \(f[i]\) 表示以 \(\textit{words}[i]\) 结尾的最长词链长度，初始时 \(f[i] = 1\)。

对于每个 \(i\)，我们枚举 \(j \in [0, i)\)。如果 \(\textit{words}[j]\) 是 \(\textit{words}[i]\) 的前身，则更新 \(f[i] = \max(f[i], f[j] + 1)\)。判断前身时，两个字符串的长度需相差 \(1\)，且较短串可由较长串删除恰好一个字符得到。

答案为 \(\max(f)\)。

时间复杂度 \(O(n^2 \times L)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是数组长度，而 \(L\) 是字符串的最大长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        def check(a: str, b: str) -> bool:
            if len(a) + 1 != len(b):
                return False
            i = 0
            for c in b:
                if i < len(a) and a[i] == c:
                    i += 1
            return i == len(a)

        words.sort(key=len)
        n = len(words)
        f = [1] * n
        for i in range(n):
            for j in range(i):
                if check(words[j], words[i]):
                    f[i] = max(f[i], f[j] + 1)
        return max(f)

 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
class Solution {
    public int longestStrChain(String[] words) {
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        int n = words.length;
        int[] f = new int[n];
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            f[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (check(words[j], words[i])) {
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
            ans = Math.max(ans, f[i]);
        }
        return ans;
    }

    private boolean check(String a, String b) {
        if (a.length() + 1 != b.length()) {
            return false;
        }
        int i = 0;
        for (int j = 0; j < b.length(); ++j) {
            if (i < a.length() && a.charAt(i) == b.charAt(j)) {
                ++i;
            }
        }
        return i == a.length();
    }
}

 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) {
        ranges::sort(words, [](const string& a, const string& b) { return a.size() < b.size(); });
        int n = words.size();
        int f[n];
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            f[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (check(words[j], words[i])) {
                    f[i] = max(f[i], f[j] + 1);
                }
            }
            ans = max(ans, f[i]);
        }
        return ans;
    }

    bool check(const string& a, const string& b) {
        if (a.size() + 1 != b.size()) {
            return false;
        }
        int i = 0;
        for (char c : b) {
            if (i < a.size() && a[i] == c) {
                ++i;
            }
        }
        return i == a.size();
    }
};

 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
func longestStrChain(words []string) int {
    sort.Slice(words, func(i, j int) bool { return len(words[i]) < len(words[j]) })
    n := len(words)
    f := make([]int, n)
    ans := 0
    for i := 0; i < n; i++ {
        f[i] = 1
        for j := 0; j < i; j++ {
            if check(words[j], words[i]) {
                f[i] = max(f[i], f[j]+1)
            }
        }
        ans = max(ans, f[i])
    }
    return ans
}

func check(a, b string) bool {
    if len(a)+1 != len(b) {
        return false
    }
    i := 0
    for j := range b {
        if i < len(a) && a[i] == b[j] {
            i++
        }
    }
    return i == len(a)
}

 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
function longestStrChain(words: string[]): number {
    const check = (a: string, b: string): boolean => {
        if (a.length + 1 !== b.length) {
            return false;
        }
        let i = 0;
        for (const c of b) {
            if (i < a.length && a[i] === c) {
                ++i;
            }
        }
        return i === a.length;
    };

    words.sort((a, b) => a.length - b.length);
    const n = words.length;
    const f: number[] = Array(n).fill(1);
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < i; ++j) {
            if (check(words[j], words[i])) {
                f[i] = Math.max(f[i], f[j] + 1);
            }
        }
    }
    return Math.max(...f);
}

 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
impl Solution {
    pub fn longest_str_chain(mut words: Vec<String>) -> i32 {
        fn check(a: &[u8], b: &[u8]) -> bool {
            if a.len() + 1 != b.len() {
                return false;
            }
            let mut i = 0;
            for &c in b {
                if i < a.len() && a[i] == c {
                    i += 1;
                }
            }
            i == a.len()
        }

        words.sort_unstable_by_key(|w| w.len());
        let n = words.len();
        let mut f = vec![1; n];
        for i in 0..n {
            for j in 0..i {
                if check(words[j].as_bytes(), words[i].as_bytes()) {
                    f[i] = f[i].max(f[j] + 1);
                }
            }
        }
        *f.iter().max().unwrap()
    }
}

方法二：动态规划 + 哈希表

思考

方法一对每个 \(i\) 扫描全部更短单词，即使长度差不是 \(1\)。前身由删去 \(w\) 的一个字符唯一确定，至多 \(L\) 个候选，可用哈希表按单词取值。

仍按长度排序，对当前 \(w\) 枚举删除一位得到的 \(p\)，用 \(f[p]+1\) 更新 \(f[w]\)。时间降为 \(O(nL^2)\)。

我们同样先将 \(\textit{words}\) 按长度排序。用哈希表 \(f\) 记录每个单词对应的最长词链长度。

对于当前单词 \(w\)，枚举删除其中一个字符得到的前身 \(p\)。若 \(p\) 已在哈希表中，则可以用 \(f[p] + 1\) 更新 \(f[w]\)。

答案为所有 \(f[w]\) 的最大值。

时间复杂度 \(O(n \times L^2)\)，空间复杂度 \(O(n \times L)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        words.sort(key=len)
        f = {}
        ans = 0
        for w in words:
            x = 1
            for i in range(len(w)):
                pred = w[:i] + w[i + 1 :]
                x = max(x, f.get(pred, 0) + 1)
            f[w] = x
            ans = max(ans, x)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int longestStrChain(String[] words) {
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        Map<String, Integer> f = new HashMap<>();
        int ans = 0;
        for (String w : words) {
            int x = 1;
            for (int i = 0; i < w.length(); ++i) {
                String pred = w.substring(0, i) + w.substring(i + 1);
                x = Math.max(x, f.getOrDefault(pred, 0) + 1);
            }
            f.put(w, x);
            ans = Math.max(ans, x);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int longestStrChain(vector<string>& words) {
        ranges::sort(words, [](const string& a, const string& b) { return a.size() < b.size(); });
        unordered_map<string, int> f;
        int ans = 0;
        for (auto& w : words) {
            int x = 1;
            for (int i = 0; i < w.size(); ++i) {
                string pred = w.substr(0, i) + w.substr(i + 1);
                x = max(x, f[pred] + 1);
            }
            f[w] = x;
            ans = max(ans, x);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func longestStrChain(words []string) int {
    sort.Slice(words, func(i, j int) bool { return len(words[i]) < len(words[j]) })
    f := map[string]int{}
    ans := 0
    for _, w := range words {
        x := 1
        for i := range w {
            pred := w[:i] + w[i+1:]
            x = max(x, f[pred]+1)
        }
        f[w] = x
        ans = max(ans, x)
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function longestStrChain(words: string[]): number {
    words.sort((a, b) => a.length - b.length);
    const f = new Map<string, number>();
    let ans = 0;
    for (const w of words) {
        let x = 1;
        for (let i = 0; i < w.length; ++i) {
            const pred = w.slice(0, i) + w.slice(i + 1);
            x = Math.max(x, (f.get(pred) || 0) + 1);
        }
        f.set(w, x);
        ans = Math.max(ans, x);
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
use std::collections::HashMap;

impl Solution {
    pub fn longest_str_chain(mut words: Vec<String>) -> i32 {
        words.sort_unstable_by_key(|w| w.len());
        let mut f = HashMap::new();
        let mut ans = 0;
        for w in words {
            let mut x = 1;
            for i in 0..w.len() {
                let pred = format!("{}{}", &w[..i], &w[i + 1..]);
                x = x.max(f.get(&pred).copied().unwrap_or(0) + 1);
            }
            f.insert(w, x);
            ans = ans.max(x);
        }
        ans
    }
}

评论