-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path1048.java
More file actions
92 lines (91 loc) · 3.33 KB
/
Copy path1048.java
File metadata and controls
92 lines (91 loc) · 3.33 KB
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// 1048. Longest String Chain
//
// You are given an array of words where each word consists of lowercase English letters.
//
// wordA is a predecessor of wordB if and only if we can insert exactly one letter anywhere in wordA without changing the order of the other characters to make it equal to wordB.
//
// For example, "abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcad".
// A word chain is a sequence of words [word1, word2, ..., wordk] with k >= 1, where word1 is a predecessor of word2, word2 is a predecessor of word3, and so on. A single word is trivially a word chain with k == 1.
//
// Return the length of the longest possible word chain with words chosen from the given list of words.
//
//
//
// Example 1:
//
// Input: words = ["a","b","ba","bca","bda","bdca"]
// Output: 4
// Explanation: One of the longest word chains is ["a","ba","bda","bdca"].
// Example 2:
//
// Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
// Output: 5
// Explanation: All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].
// Example 3:
//
// Input: words = ["abcd","dbqca"]
// Output: 1
// Explanation: The trivial word chain ["abcd"] is one of the longest word chains.
// ["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.
//
//
// Constraints:
//
// 1 <= words.length <= 1000
// 1 <= words[i].length <= 16
// words[i] only consists of lowercase English letters.
//
// Runtime 107 ms Beats 12.15%
// Memory 43.4 MB Beats 45.65%
class Solution {
public int longestStrChain(String[] words) {
Arrays.sort(words, (a, b) -> a.length() - b.length());
int[] counts = new int[words.length];
Arrays.fill(counts, 1);
int max = 1;
for (int i = 1; i < counts.length; i++) {
for (int j = i - 1; j >= 0; j--) {
if (words[i].equals(words[j])) {
counts[i] = counts[j];
continue;
} else if (words[i].length() == words[j].length()) {
continue;
} else if (words[i].length() > words[j].length() + 1) {
break;
}
int indexR = 0;
int indexL = 0;
while (indexR < words[i].length() && indexL < words[j].length()) {
if (words[i].charAt(indexR) == words[j].charAt(indexL)) {
indexL++;
}
indexR++;
}
if (indexL == words[j].length()) {
counts[i] = Math.max(counts[i], counts[j] + 1);
}
}
max = Math.max(counts[i], max);
}
return max;
}
}
// Runtime 48 ms Beats 47.77%
// Memory 44 MB Beats 25.91%
class Solution {
public int longestStrChain(String[] words) {
Arrays.sort(words, (a, b) -> a.length() - b.length());
Map<String, Integer> counts = new HashMap<>();
int max = 1;
for (String word: words) {
int count = 1;
for (int i = 0; i < word.length(); i++) {
String prev = word.substring(0, i) + word.substring(i + 1);
count = Math.max(count, counts.getOrDefault(prev, 0) + 1);
}
counts.put(word, count);
max = Math.max(max, count);
}
return max;
}
}