Q19 Alien Dictionary | Practice | GeeksforGeeks
Tue Apr 25 2023 12:38:36 GMT+0000 (Coordinated Universal Time)
Saved by @Ayush_dabas07
//{ Driver Code Starts /*package whatever //do not write package name here */ import java.io.*; import java.util.*; import java.math.*; class GFG { public static void main (String[] args) { Scanner sc = new Scanner(System.in); int t = Integer.parseInt(sc.next()); while(t-- > 0) { int n = Integer.parseInt(sc.next()); int k = Integer.parseInt(sc.next()); String[] words = new String[n]; for(int i=0;i<n;i++) { words[i] = sc.next(); } Solution ob = new Solution(); // System.out.println(T.findOrder(words,k)); String order = ob.findOrder(words,n,k); if(order.length() == 0){ System.out.println(0); continue; } String temp[] = new String[n]; for(int i=0;i<n;i++) temp[i] = words[i]; Arrays.sort(temp, new Comparator<String>(){ @Override public int compare(String a, String b) { int index1 = 0; int index2 = 0; for(int i = 0; i < Math.min(a.length(), b.length()) && index1 == index2; i++) { index1 = order.indexOf(a.charAt(i)); index2 = order.indexOf(b.charAt(i)); } if(index1 == index2 && a.length() != b.length()) { if(a.length() < b.length()) return -1; else return 1; } if(index1 < index2) return -1; else return 1; } }); int flag = 1; for(int i=0;i<n;i++) { if(!words[i].equals(temp[i])) { flag = 0; break; } } System.out.println(flag); } } } // } Driver Code Ends //User function Template for Java class Solution { public String findOrder(String [] dict, int n, int k) {//doesn't work on GFG , take a look once HashMap<Character , HashSet<Character>> graph = new HashMap<>(); HashMap<Character,Integer> indegree = new HashMap<>(); for(String word : dict){ for(char ch : word.toCharArray()) indegree.put(ch , 0); } //making graph between letters for(int i = 1 ; i < dict.length ; i++){ String word1 = dict[i-1] , word2 = dict[i]; int len = Math.min(word1.length() , word2.length()); // System.out.println(word1 +" " + word2); for(int j = 0 ; j < len ; j++){ char ch1 = word1.charAt(j) , ch2 = word2.charAt(j); // System.out.println(ch1 +" " + ch2); if(ch1 != ch2){ //making edge between ch1 and ch2 HashSet<Character> temp = graph.getOrDefault(ch1 , new HashSet<>()); temp.add(ch2); graph.put(ch1 , temp); //increasing indegree of ch2 , and puttin indegree of ch1 = 0 indegree.put(ch2 , indegree.getOrDefault(ch2,0)+1); if(indegree.containsKey(ch1) == false) indegree.put(ch1 , 0); break; } } //calling kahn's algo } return kahn(graph , indegree); } public String kahn(HashMap<Character , HashSet<Character>> graph, HashMap<Character,Integer> indegree){ StringBuilder sb = new StringBuilder(); LinkedList<Character> q = new LinkedList<>(); //adding all nodes with indegree 0 for(char ch : indegree.keySet()){ if(indegree.get(ch) == 0) q.addLast(ch); } //firing kahn while(q.size()>0){ char ch = q.removeFirst(); sb.append(ch+""); //reducing indegree of its neighours if(graph.containsKey(ch)){ for(char nbr : graph.get(ch)){ indegree.put(nbr , indegree.get(nbr)-1); //if indegree becomes 0 remove it and add to q if(indegree.get(nbr) == 0){ indegree.remove(nbr); q.addLast(nbr); } } } } return sb.toString(); } }
Comments