https://leetcode.com/problems/longest-string-chain/

Solution.java

class Solution {
    public int longestStrChain(String[] words) {
        System.out.println(isPred("bca","bda"));
        Arrays.sort(words);
        List<String> maxList = new ArrayList<>();
        Map<String, List<String>> map;
        Graph<String> graph = new Graph();
        for(int i = 0;i<words.length;i++) {
            for(int j = i+1;j<words.length;j++) {
                if(words[i].length()!=words[j].length()-1) break;
                if(isPred(words[i], words[j])) {
                    graph.addNode(words[i]);
                    graph.addNode(words[j]);
                    graph.addEdge(words[i], words[j]);
                }
            }
        }
        Integer max = Integer.MIN_VALUE;
        map = graph.getMap();
        for(String key: map.keySet()) {
            List<String> l = graph.dfs(key);
            if(l.size()>max){
                max = l.size();;
                maxList = l;
            }
            max = Math.max(max, graph.dfs(key).size());
        }
        System.out.println("maxList "+maxList);
        return max;
    }
    
    private boolean isPred(String word1, String word2) {
        if(word1.length()!=word2.length()-1) return false;
        
        Map<Character, Integer> map = new HashMap<>();
        for(int i = 0;i<word2.length();i++) {
            map.putIfAbsent(word2.charAt(i), 0);
            map.put(word2.charAt(i), map.get(word2.charAt(i))+1);
        }
        int diff = 0;
        
        for(int i = 0;i<word1.length();i++) {
            char c = word1.charAt(i);
            if(!map.containsKey(c)) return false;
            map.put(c, map.get(c)-1);
            if(map.get(c)==0) map.remove(c);
        }
        return map.size()==1;
    }
    
    class Graph<T> {
        private Map<T, List<T>> map;
        Integer longest;

        
        Graph() {
            map = new HashMap<>();
            longest = Integer.MIN_VALUE;
        }
        
        public Map<T, List<T>> getMap() {
            return map;
        }
        
        public void addNode(T obj) {
            if(!map.containsKey(obj))
                map.put(obj, new ArrayList<>());
        }
        
        public void addEdge(T obj1, T obj2) {
            if(!map.containsKey(obj1) && !map.containsKey(obj2)) {
                throw new NullPointerException("Neither object exists in the graph");
            }

            if(!map.get(obj1).contains(obj2)) {
                map.get(obj1).add(obj2);
            }
        }
        
        public List<T> dfs(T obj) {
            if(!map.containsKey(obj)) return new ArrayList<>();
            List<T> list = new ArrayList<>();
            Set<T> visited = new HashSet<>();
            helper(obj, list, visited);
            return list;
        }
        
        private Integer helper(T obj, List<T> list, Set<T> visited) {
            if(visited.contains(obj)) return 0;
            visited.add(obj);
            list.add(obj);
            for(T t: map.get(obj)) {
                helper(t, list, visited);
            }
        }
        
        
    }
}