题目

Given a list of words, each word consists of English lowercase letters.

Let’s say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2. For example, "abc" is a predecessor of "abac".

A word chain is a sequence of words [word_1, word_2, ..., word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.

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

Example 1:

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

Example 2:

  1. Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
  2. Output: 5

Constraints:

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

题意

如果字符串s2能够通过在字符串s1的某一个位置插入一个字符后得到，那么说s1是s2的”前辈”。给定一个字符串数组，从中选取若干个组成一个序列，使该序列中每一个字符串都是后一个字符串的前辈，求这样的序列的最大长度。

思路

动态规划。将数组按照字符串长度排序，问题就变得和LIS问题类似，使用相同的方法解决即可。

代码实现

Java

  1. class Solution {
  2.     public int longestStrChain(String[] words) {
  3.         int ans = 0;
  4.         int[] dp = new int[words.length];
  5.         Arrays.fill(dp, 1);
  6.         Arrays.sort(words, (a, b) -> a.length() - b.length());
  8.         for (int i = 1; i < words.length; i++) {
  9.             for (int j = 0; j < i; j++) {
  10.                 if (judge(words[j], words[i])) {
  11.                     dp[i] = Math.max(dp[i], dp[j] + 1);
  12.                 }
  13.             }
  14.             ans = Math.max(ans, dp[i]);
  15.         }
  17.         return ans;
  18.     }
  20.     private boolean judge(String a, String b) {
  21.         if (a.length() +1!= b.length()) return false;
  23.         int i = 0, j = 0;
  24.         while (i < a.length() && j < b.length()) {
  25.             if (a.charAt(i) == b.charAt(j)) i++;
  26.             j++;
  27.         }
  29.         return i == a.length() && b.length() - j <= 1;
  30.     }
  31. }