-
Notifications
You must be signed in to change notification settings - Fork 7
/
Main.java
44 lines (39 loc) · 1.27 KB
/
Main.java
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
package com.company;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
String[] words = {"bqtmbnugq","bjqtmbnuwsgq","m","hkgszenh","zmucnwn","kgzn","yjmk"};
System.out.println(longestStrChain(words));
}
public static int longestStrChain(String[] words) {
Arrays.sort(words, (a, b) -> a.length() - b.length());
int[] dp = new int[words.length];
dp[0] = 1;
int res = 1;
for (int i = 1; i < dp.length; i++) {
int max = 1;
for (int j = i - 1; j >= 0; j--) {
if (dp[j] + 1 <= max) continue;
if (isPredecessor(words[j], words[i]))
max = Math.max(max, dp[j] + 1);
}
dp[i] = max;
res = Math.max(res, dp[i]);
}
return res;
}
public static boolean isPredecessor(String s1, String s2) {
if (s1.length() + 1 != s2.length()) return false;
int p1 = 0, p2 = 0, count = 0;
while (p1 < s1.length() && p2 < s2.length()) {
if (s1.charAt(p1) == s2.charAt(p2))
p1++;
else {
if (count == 1) return false;
count++;
}
p2++;
}
return true;
}
}