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
| class Solution {
public int longestStrChain(String[] words) {
Map<String, Integer> memo = new HashMap<>();
Set<String> wordSet = new HashSet<>();
Collections.addAll(wordSet, words);
int ans = 0;
for (String word : words) {
ans = Math.max(ans, helper(word, memo, wordSet));
}
return ans;
}
private int helper(String word, Map<String, Integer> memo, Set<String> wordSet) {
if (memo.containsKey(word)) {
return memo.get(word);
}
StringBuilder currWord = new StringBuilder(word);
int maxLength = 1;
for (int i = 0; i < currWord.length(); i++) {
currWord.deleteCharAt(i);
String newWord = currWord.toString();
if (wordSet.contains(newWord)) {
maxLength = Math.max(maxLength, helper(newWord, memo, wordSet) + 1);
}
currWord.insert(i, word.charAt(i));
}
memo.put(word, maxLength);
return maxLength;
}
}
|
标准的recursion + memoization.
我们假设每个word都是chain的最后一个, 然后尝试删除其中每一个位置的char, 之后得到的String看在words里面有没有, 如果有继续这个操作, 看能凑成多大. 由于一个word可以在多个chain出现, 因此我们如果计算完某个word作为end时的chain length, 我们把结果存到memo中.
注意的是19行不能初始化为0而必须是1. 因为可能当前的word没有precursor, 也就是for循环里面的if一直不会被触发, 如果maxLength初始化为0, 那么最后得出来的结果就是当前word构成的chain的最长长度是0, 但实际上应该是1. 这点要注意.
第6行ans也要初始化为0, 因为可能words是空的.
时间复杂度和空间复杂度具体见1048的解析
时间复杂度: O(N + NL^2) = O(NL^2) 对于一个word我们遍历所有的位置, 删除一个char是O(L), 遍历所有位置也是O(L)乘在一起就是O(L^2). 由于一共N个word, 那就是O(NL^2). 由于使用memoization, 每个word只会被traverse一遍.
空间复杂度: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int longestStrChain(String[] words) {
Arrays.sort(words, (a, b) -> (a.length() - b.length()));
Map<String, Integer> memo = new HashMap<>();
int ans = 0;
for (String word : words) {
StringBuilder sb = new StringBuilder(word);
int maxLength = 1;
for (int i = 0; i < word.length(); i++) {
sb.deleteCharAt(i);
String newWord = sb.toString();
maxLength = Math.max(maxLength, memo.getOrDefault(newWord, 0) + 1);
sb.insert(i, word.charAt(i));
}
ans = Math.max(ans, maxLength);
memo.put(word, maxLength);
}
return ans;
}
}
|
有recursion + memoization这种top-down, 自然就要DP这种bottom-up的解法. 我们观察之前的解法的base case无非就是一路往下找, 能找到最短的. 或者中途找不到别的满足chain的string直接返回. 于是我们从最短的开始找起. 我们先把words给sort一下, 然后从左边开始去遍历. 一样的道理, 对于每个word, 把每个位置的char删掉, 看有没有之前短的word能和我们构成chain. 由于我们是从小到大去做的, 那么一个word删除某个位置的char后通过访问map就能知道是否有与自己匹配的word, 如果有, 那说明这个word我们之前已经计算过, 那么直接返回以这个word为end的chain的最长长度给到我们, 我们拿到这个长度后 + 1即为目前以我们自己为end的的chain的长度. 然后更新maxLength即可.
时间复杂度: sort是nlogn, 一共N个word, 每个word是遍历L个位置, 每个位置的删除插入操作是O(L)合在一起是O(NL^2). 再和之前的sort和在一起就是O(N(L^2 + logN))
空间复杂度: O(N) 用了map.
