05 August 2008
给你一个单词数组，其中每个单词由小写英文字母组成。
wordA 是 wordB 的前身当且仅当我们可以在 wordA 的任意位置准确插入一个字母而不改变其他字符的顺序以使其等于 wordB。
例如，“abc”是“abac”的前身，而“cba”不是“bcad”的前身。 一个词链是一个词序列 [word1, word2, …, wordk]，其中 k >= 1，其中 word1 是 word2 的前身，word2 是 word3 的前身，以此类推。单个单词通常是具有 k == 1 的单词链。
返回从给定单词列表中选择的单词的最长可能单词链的长度。
不用排序
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
class Solution {
public int longestStrChain(String[] words) {
List<Set<String>> wordLen = new ArrayList(16);
Map<String, Integer> lengthMap = new HashMap();
int result = 1;
for(int i = 0; i < 16; ++i) {
wordLen.add(new HashSet<String>());
}
for(String word : words) {
int len = word.length();
wordLen.get(len - 1).add(word);
}
for(int i = 1; i < wordLen.size(); ++i) {
Set<String> currLength = wordLen.get(i);
if(currLength.isEmpty()) {
continue;
}
Set<String> prevLength = wordLen.get(i - 1);
if(prevLength.isEmpty()) {
continue;
}
for(String word : currLength) {
int len = word.length();
int max = 0;
for(int j = 0; j < len; ++j) {
String sub = word.substring(0, j) + word.substring(j + 1);
if(prevLength.contains(sub)) {
max = Math.max(max, lengthMap.getOrDefault(sub, 1) + 1);
}
}
if(max != 0) {
result = Math.max(result, max);
lengthMap.put(word, max);
}
}
}
return result;
}
}
DP + sorting
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) {
var n = words.length;
Arrays.sort(words, (a, b) -> a.length() - b.length());
var nextRangeIdx = new int[n];
nextRangeIdx[n - 1] = n;
for (int i = n - 2; i >= 0; i--)
nextRangeIdx[i] = words[i].length() == words[i + 1].length()
? nextRangeIdx[i + 1]
: i + 1;
var dp = new int[words.length];
for (int curIdx = n - 1; curIdx >= 0; curIdx--) {
var curWord = words[curIdx];
var nextIdx = nextRangeIdx[curIdx];
var maxSeq = 1;
while (nextIdx < words.length && curWord.length() + 1 == words[nextIdx].length()) {
if (predecessor(curWord, words[nextIdx]))
maxSeq = Math.max(maxSeq, dp[nextIdx] + 1);
nextIdx++;
}
dp[curIdx] = maxSeq;
}
var max = 0;
for (int len : dp)
if (len > max)
max = len;
return max;
}
boolean predecessor(String pre, String cur) {
var p = 0;
var c = 0;
var inserted = false;
while (p < pre.length() && c < cur.length()) {
if (pre.charAt(p) == cur.charAt(c)) {
p++;
} else {
if (inserted)
return false;
inserted = true;
}
c++;
}
return true;
}
}