Longest String Chain

1、题目

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:

Input: ["a","b","ba","bca","bda","bdca"] Output: 4 Explanation: one of the longest word chain is "a","ba","bda","bdca".

 

Note:

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

      题目大意是给出一个字符串数组，从中挑选出最长的字串序列 [word_1, word_2, ..., word_k]满足word_1是word_2的predecessor， word_2是word_3是predecessor。其中word_1是word_2的predecessor当且仅当在word_1任意位置添加一个字符使得word_1和word_2相等。

2、解题思路：动态规划

       递推式：定义result[i]表示为以words[i]作为字符链结尾的word,得到递推式：result[i] = max(result[j] + 1 (条件：words[j] 能够作为words[i]的predecessor), result[i]) ( 0 <= j < i)

3、 坑点

   没有说一定要按照给出的顺序进行挑选，因此第一步应该是要按照word的长度进行排序。

4、代码

class Solution { public int longestStrChain(String[] words) { Arrays.sort(words, Comparator.comparingInt(String::length)); int[] result = new int[words.length]; for (int i = 0; i < result.length; i++){ result[i] = 1; } int max = 1; for (int i = 1; i < words.length; i++){ for (int j = 0; j < i; j++){ if (isPredecessor(words[j], words[i])){ result[i] = Math.max(result[j] + 1, result[i]); max = Math.max(max, result[i]); } } } return max; } public boolean isPredecessor(String str1, String str2){ if (str1.length() + 1 != str2.length()){ return false; } int index2 = 0; int index1 = 0; while (index1 < str1.length() && index2 < str2.length()){ if (str1.charAt(index1) == str2.charAt(index2)){ index1++; index2++; } else if ((index2 + 1 < str2.length()) && (str1.charAt(index1) == str2.charAt(index2 + 1))){ index1++; index2 += 2; } else { return false; } } return index1 == str1.length() && ((index2 == str2.length()) || (index2 == str2.length() -1)); } }

改进版：

class Solution { public int longestStrChain(String[] words) { Arrays.sort(words, Comparator.comparingInt(String::length)); int[] result = new int[words.length]; int max = Integer.MIN_VALUE; for (int i = 0; i < words.length; i++) { result[i] = 1; for (int j = 0; j < i; j++) { if (isPredecessor(words[j], words[i])) { result[i] = Math.max(result[j] + 1, result[i]); } } max = Math.max(max, result[i]); } return max; } public boolean isPredecessor(String str1, String str2){ if (str1.length() + 1 != str2.length()){ return false; } for (int index1 = 0, index2 = 0, diff = 0; index1 < str1.length(); ){ if (str1.charAt(index1) == str2.charAt(index2)){ index1++; index2++; } else { diff++; if (diff > 1) { return false; } index2 ++; } } return true; } }