【动态规划】
给出一个单词列表，其中每个单词都由小写英文字母组成。
如果我们可以在 word1 的任何地方添加一个字母使其变成 word2，那么我们认为 word1 是 word2 的前身。例如，"abc" 是 "abac" 的前身。
词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，其中 word_1 是 word_2 的前身，word_2 是 word_3 的前身，依此类推。
从给定单词列表 words 中选择单词组成词链，返回词链的最长可能长度。
Example:
示例：
输入：["a","b","ba","bca","bda","bdca"]
输出：4
解释：最长单词链之一为 "a","ba","bda","bdca"。
提示：
1 <= words.length <= 10001 <= words[i].length <= 16words[i] 仅由小写英文字母组成。
Analysis
定义$dp[i]$ 表示 到 $words[i]$ 为止最长的词链长度.
这里有一点瑕疵，暂时在每个循环里只能得到以固定字符串为起点的最长词链长度，因此结果需要再次遍历。
具体分析可以在注释查看
Solution 【动态规划】 ( 119ms)
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
47
48
49
50
51
52
|
class Solution {
public int longestStrChain(String[] words) {
int len = words.length;
/* 将字符串按照字典序重新排列 */
Arrays.sort(words, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return Integer.compare(o1.length(), o2.length());
}
});
/* dp[i] 表示 到 words[i] 为止最长的词链长度 */
int[] dp = new int[len];
for(int i = 0; i < len - 1; i++) {
String a = words[i];
for (int j = i + 1; j < len; j++) {
String b = words[j];
/* 判断 words[i] 是否是 words[j] 的前身 */
if (isPredecessor(a, b)) {
dp[j] = Math.max(dp[j], dp[i]+1);
}
}
}
/* 得到最终结果，由于最末尾的字符串不一定在最终词链里，因此dp[len-1]不一定是最终结果 */
int res = 0;
for (int i = 0; i < len; i++) {
if (res < dp[i]) res = dp[i];
}
return res + 1;
}
private boolean isPredecessor(String stra, String strb) {
int i = 0; // 字符串A的指针
int j = 0; // 字符串B的指针
int lenA = stra.length();
int lenB = strb.length();
/* 排除长度相差不为一的情况 */
if (lenA != lenB-1) {
return false;
}
char[] a = stra.toCharArray();
char[] b = strb.toCharArray();
while (i < lenA && j < lenB) {
if (a[i] == b[j]) {
i++;
}
j++;
}
return i == lenA;
}
}
|
复杂度分析
时间：$O(N^2)$
空间：$O(N)$
Solution 【动态规划】(40ms) 官方目前最快答案
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
class Solution {
public ArrayList<ArrayList<String>> list = new ArrayList<>();
public int maxLen = 1;
public int[][] dp = new int[17][1000];
public int longestStrChain(String[] words) {
for(int i = 0;i < dp.length;i++) {
ArrayList<String> subList = new ArrayList<String>();
list.add(subList);
}
for(String string : words) {
list.get(string.length()-1).add(string);
}
for(int i = 0;i < dp.length;i++) {
ArrayList<String> tempList = list.get(i);
for(int j = 0;j < tempList.size();j++) {
longestStrChain(tempList.get(j),i+1,1,j);
}
}
return maxLen;
}
public int longestStrChain(String preString,int index,int len,int subIndex) {
if(index == 17 || list.get(index).size() == 0) {
if(maxLen < len)
maxLen = len;
return len;
}else {
//System.out.println("index-1"+(index-1)+"::subIndex"+subIndex);
if(dp[index-1][subIndex] != 0)
return dp[index-1][subIndex];
ArrayList<String> tempList = list.get(index);
int max = len;
for(int i = 0;i < tempList.size();i++) {
String string = tempList.get(i);
if(checkPreStr(preString.toCharArray(), string.toCharArray())) {
dp[index][i] = longestStrChain(string,index+1,len+1,i);
if(dp[index][i] > max)
max = dp[index][i];
}
}
dp[index-1][subIndex] = max;
if(maxLen < max)
maxLen = max;
return max;
}
}
public boolean checkPreStr(char[] preStr,char[] str) {
int i = 0,j = 0,flag = 0;
for(;i < preStr.length && j < str.length;i++,j++) {
if(preStr[i] != str[j] && flag == 0) {
i--;
flag = 1;
}else if(preStr[i] != str[j] && flag == 1) {
return false;
}
}
return true;
}
}
|