package leetcode;

/**
 * https://leetcode.com/problems/longest-string-chain/
 */
public class Problem1048 {
    public int longestStrChain(String[] words) {
        // TODO
        return 0;
    }

    public static void main(String[] args) {
        Problem1048 prob = new Problem1048();
        System.out.println(prob.longestStrChain(new String[]{"a", "b", "ba", "bca", "bda", "bdca"})); // 4
    }
}

@@ -12,16 +12,116 @@
 tcode;%0A%0A
+import java.util.ArrayList;%0Aimport java.util.HashMap;%0Aimport java.util.List;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -263,238 +263,1569 @@
     
-// TODO%0A        return 0;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1048 prob = new Problem1048();%0A        System.out.println(prob.longestStrChain(new String%5B%5D%7B%22a%22, %22b%22, %22ba%22, %22bca%22, %22bda%22, %22bdca%22%7D)); // 4
+Map%3CInteger, List%3CString%3E%3E map = new HashMap%3C%3E();%0A        for (String word : words) %7B%0A            if (!map.containsKey(word.length())) %7B%0A                map.put(word.length(), new ArrayList%3C%3E());%0A            %7D%0A            map.get(word.length()).add(word);%0A        %7D%0A        int answer = 0;%0A        Map%3CString, Integer%3E memo = new HashMap%3C%3E();%0A        for (String word : words) %7B%0A            answer = Math.max(answer, longestStrChain(map, word, memo) + 1);%0A        %7D%0A        return answer;%0A    %7D%0A%0A    private static int longestStrChain(Map%3CInteger, List%3CString%3E%3E words, String word,%0A                                       Map%3CString, Integer%3E memo) %7B%0A        if (!words.containsKey(word.length() + 1)) %7B%0A            return 0;%0A        %7D%0A        if (memo.containsKey(word)) %7B%0A            return memo.get(word);%0A        %7D%0A        int max = 0;%0A        for (String s : words.get(word.length() + 1)) %7B%0A            if (isValid(word, s)) %7B%0A                max = Math.max(max, longestStrChain(words, s, memo) + 1);%0A            %7D%0A        %7D%0A        memo.put(word, max);%0A        return max;%0A    %7D%0A%0A    private static boolean isValid(String word1, String word2) %7B%0A        int%5B%5D counts1 = new int%5B26%5D;%0A        for (char c : word1.toCharArray()) %7B%0A            counts1%5Bc - 'a'%5D++;%0A        %7D%0A        int%5B%5D counts2 = new int%5B26%5D;%0A        for (char c : word2.toCharArray()) %7B%0A            counts2%5Bc - 'a'%5D++;%0A        %7D%0A        int diff = 0;%0A        for (int i = 0; i %3C counts1.length; i++) %7B%0A            diff += Math.abs(counts2%5Bi%5D - counts1%5Bi%5D);%0A        %7D%0A        return diff == 1;
 %0A   

Solve problem 1048