1048. Longest String Chain

这是一道常规题。
very straightforward problem.
build the graph first.
Traverse the graph and find the longest path you can have.
I am using depth first search while using memo to speed thing up.

class Solution {
    public int longestStrChain(String[] words) {
        Map<Integer, List<Integer>> lenList = new HashMap<>();
        int min = Integer.MAX_VALUE, max = 0;
        for (int i = 0; i < words.length; i++) {
            int len = words[i].length();
            lenList.putIfAbsent(len, new ArrayList<>());
            lenList.get(len).add(i);
            min = Math.min(min, len);
            max = Math.max(max, len);
        }
        Map<Integer, List<Integer>> graph = new HashMap<>();
        buildGraph(words, graph, lenList, min, max); //build graph
        Map<Integer, Integer> maxLength = new HashMap<>(); // hashMap for memo
        int ans = 0;
        for (int i = 0; i < words.length; i++) {
            ans = Math.max(ans, dfs(i, maxLength, graph)); // DFS
        }
        return ans;
    }
  
    
    private int dfs(int index, Map<Integer, Integer> mem,  Map<Integer, List<Integer>> graph) {
        if (mem.containsKey(index)) return mem.get(index);
        if (graph.get(index) == null) {
            mem.put(index, 1);
            return 1;
        }
        int ans = 1;
        for (int downStream : graph.get(index)) ans = Math.max(ans, 1 + dfs(downStream, mem, graph));
        mem.put(index, ans);
        return ans;
    }
    
    private void buildGraph(String[] words, Map<Integer, List<Integer>> graph, 
                            Map<Integer, List<Integer>> lenList, int min, int max) {
        for (int len = min; len < max; len++) {
            List<Integer> lenWords = lenList.get(len);
            List<Integer> lenPlusOneWords = lenList.get(len + 1);
            if (lenWords == null || lenPlusOneWords == null 
                || lenWords.size() == 0 || lenPlusOneWords.size() == 0) continue;
            
            for (int m : lenWords) {
                for (int n : lenPlusOneWords) {
                    boolean res = isPredecessor(words[m], words[n]);
                    if (isPredecessor(words[m], words[n])) {
                        graph.putIfAbsent(m, new ArrayList<>());
                        graph.get(m).add(n);
                    }
                }
            }
        }
    }
    private boolean isPredecessor(String w1, String w2) {
        if (w1 == null || w2 == null) return false;
        if (w1.length() + 1 != w2.length()) return false;
        for (int i = 0; i < w1.length(); i++) {
            if (w1.charAt(i) != w2.charAt(i))  return match(w1, i, w2);
        }
        return true;
    }
    private boolean match(String w1, int i, String w2) {
        while (i < w1.length()) {
            if (w1.charAt(i) != w2.charAt(++i)) return false;
        }
        return true;
    }
}