Longest String Chain LeetCode solution in Java

1
class Solution {
2

3
  Boolean compareForIncreaseByOne(String str1, String str2) {
4
    // str 1 will be long than str2
5
    int first = 0;
6
    int second = 0;
7
    if (str1.length() != (str2.length() + 1)) {
8
      return false;
9
    }
10
    while (first < str1.length()) {
11
      if (second < str2.length() && str1.charAt(first) == str2.charAt(second)) {
12
        first++;
13
        second++;
14
      } else {
15
        first++;
16
      }
17
    }
18
    if (first == str1.length() && second == str2.length()) {
19
      return true;
20
    }
21
    return false;
22
  }
23

24
  public int longestStrChain(String[] words) {
25
    int N = words.length;
26
    Arrays.sort(words, (a, b) -> a.length() - b.length()); // as Sequence/Subset are not ordered
27
    int[] dp = new int[N];
28
    Arrays.fill(dp, 1);
29
    int maxi = 1;
30
    for (int i = 0; i < N; i++) {
31
      for (int j = 0; j < i; j++) {
32
        if (compareForIncreaseByOne(words[i], words[j]) && dp[j] + 1 > dp[i]) {
33
          dp[i] = dp[j] + 1;
34
          maxi = Math.max(maxi, dp[i]);
35
        }
36
      }
37
    } // for neds
38
    return maxi;
39
  }
40
}