原文链接: https://leetcode-cn.com/problems/longest-string-chain

英文原文

You are given an array of words where each word consists of lowercase English letters.

wordA is a predecessor of wordB if and only if we can insert exactly one letter anywhere in wordA without changing the order of the other characters to make it equal to wordB.

• For example, "abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcad".

A word chain is a sequence of words [word1, word2, ..., wordk] with k >= 1, where word1 is a predecessor of word2, word2 is a predecessor of word3, and so on. A single word is trivially a word chain with k == 1.

Return the length of the longest possible word chain with words chosen from the given list of words.

 

Example 1:

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: One of the longest word chains is ["a","ba","bda","bdca"].

Example 2:

Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output: 5
Explanation: All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

Example 3:

Input: words = ["abcd","dbqca"]
Output: 1
Explanation: The trivial word chain ["abcd"] is one of the longest word chains.
["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.

 

Constraints:

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 16
• words[i] only consists of lowercase English letters.

中文题目

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

如果我们可以在 word1 的任何地方添加一个字母使其变成 word2，那么我们认为 word1 是 word2 的前身。例如，"abc" 是 "abac" 的前身。

词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，其中 word_1 是 word_2 的前身，word_2 是 word_3 的前身，依此类推。

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

示例：

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

 

提示：

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

 

通过代码

高赞题解

1048. 最长字符串链 Medium

方法1：DP

• dp[i]表示从words[0]到words[i]最长的词链长度

将字母按字符长度字典序排序的代码

Arrays.sort(words, new Comparator<String>() {
      @Override
      public int compare(String o1, String o2) {
          return o1.length() - o2.length();
      }
  });

[]
public int longestStrChain(String[] words) {
    Arrays.sort(words, Comparator.comparingInt(String::length));
    int n = words.length;
    int[] dp = new int[n];
    int res = 0;
    for (int i = 0; i < n; i++) {
        String a = words[i];
        for (int j = i + 1; j < n; j++) {
            String b = words[j];
            if (isPredecessor(a, b)) {
                dp[j] = Math.max(dp[j], dp[i] + 1);
                res = Math.max(dp[j], res);
            }
        }
    }
    return res + 1;
}

/**
 * 判断a是否是b的前身 是返回true 如 "bda" 是"bdca"的前身
 *
 * @param a
 * @param b
 * @return
 */
private boolean isPredecessor(String a, String b) {
    int i = 0, j = 0;
    int m = a.length(), n = b.length();
    if ((m + 1) != n) return false;
    while (i < m && j < n) {
        if (a.charAt(i) == b.charAt(j)) i++;
        j++;
    }
    return i == m;
}

[]
print('Hello world!')

方法2：改进版DP

• 根据题意1 <= words[i].length <= 16 ==>arr存放的是17个长度的辅助数组，存的是words的同一字符长度的最末的下标
• dp[i]表示从words[0]到words[i]最长的词链长度

[]
public int longestStrChain1st(String[] words) {
    Arrays.sort(words, Comparator.comparingInt(String::length));
    int[] arr = new int[17];
    Arrays.fill(arr, -1);
    int n = words.length;
    for (int i = 0; i < n; i++) {
        arr[words[i].length()] = i;
    }
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int res = 0;
    for (int i = 0; i < n; i++) {
        int target = words[i].length() - 1;
        int index = arr[target];
        while (index >= 0 && words[index].length() == target) {
            if (isPredecessor(words[index], words[i])) {
                dp[i] = Math.max(dp[i], dp[index] + 1);
            }
            index--;
        }
        res = Math.max(dp[i], res);
    }
    return res;
}

[]
print('Hello world!')

方法3：DFS

[]
int res = 0;

public int longestStrChain2nd(String[] words) {
    int min = 0, max = 16;//最小字符长度，最大字符长度
    //K为字符长度，Set为该字符长度的word集合
    Map<Integer, Set<String>> map = new HashMap<>();
    for (String word : words) {
        map.putIfAbsent(word.length(), new HashSet<>());
        map.get(word.length()).add(word);
        min = Math.min(min, word.length());
        max = Math.max(max, word.length());
    }
    for (int len = min; len <= max; len++) {
        Set<String> curSet = map.get(len);
        if (curSet == null) continue;//当set没有值时，无需遍历
        if ((max + 1 - len <= res)) continue;//最大长度+1-当前的长度<=res，res更加符合题意
        for (String cur : curSet) {
            findNext(map, len, cur);
        }
    }
    return res;
}

/**
 * @param map
 * @param len 当前字符的长度
 * @param levelStr 当前字符
 */
private void findNext(Map<Integer, Set<String>> map, int len, String levelStr) {
    res = Math.max(res, levelStr.length() + 1 - len);//记录结果集
    Set<String> curSet = map.get(levelStr.length() + 1);//
    if (curSet == null) return;//退出条件
    Iterator<String> it = curSet.iterator();
    while (it.hasNext()) {
        String next = it.next();
        if (isPredecessor(levelStr, next)) {
            findNext(map, len, next);
            it.remove();
        }
    }
}

[]
print('Hello world!')

---

---

更多内容，欢迎订阅

统计信息

通过次数	提交次数	AC比率
10717	23254	46.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言