Skip to content

Instantly share code, notes, and snippets.

@rohandalvi
Created December 3, 2019 03:56
Show Gist options
  • Save rohandalvi/8129a385388e0e2882e4e7f5b1cd71f8 to your computer and use it in GitHub Desktop.
Save rohandalvi/8129a385388e0e2882e4e7f5b1cd71f8 to your computer and use it in GitHub Desktop.
class Solution {
private boolean isPred(String a, String b) {
int diff = 0;
if(a.length() != b.length()-1) return false;
for(int i = 0 , j = 0;i<a.length() && j<b.length() ;) {
if(a.charAt(i) == b.charAt(j)) {
i++;
j++;
} else {
if(diff>0) return false;
diff++;
j++;
}
}
return true;
}
public int longestStrChain(String[] words) {
int[] dp = new int[words.length];
Integer max = Integer.MIN_VALUE;
for(int i = 0;i<dp.length;i++) dp[i]=1;
Arrays.sort(words, new Comparator<String>() {
public int compare(String s1, String s2) {
return s1.length() - s2.length();
}
});
for(int j = 1; j<words.length;j++) {
for(int i = 0;i<j; i++) {
if(isPred(words[i], words[j])) {
dp[j] = Math.max(dp[j], 1+dp[i]);
max = Math.max(max, dp[j]);
}
}
}
//System.out.println(Arrays.toString(dp));
return Math.max(1, max);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment