Created
December 3, 2019 03:39
-
-
Save rohandalvi/b3db9815737d8509d573b7efc54d66c1 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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); | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment