Created
June 27, 2021 02:51
-
-
Save adeydas/c0bbcfe463c784c39e9de6534ca3fd04 to your computer and use it in GitHub Desktop.
AlienDictionary.java
This file contains hidden or 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
| import java.util.*; | |
| import java.util.stream.*; | |
| class Scratchpad { | |
| // There is a dictionary containing words from an alien language for which we don’t know the ordering of the alphabets. | |
| // Write a method to find the correct order of the alphabets in the alien language. It is given that the input is a valid dictionary and there exists an ordering among its alphabets. | |
| // Example 1: | |
| // Input: Words: ["ba", "bc", "ac", "cab"] | |
| // Output: bac | |
| // Explanation: Given that the words are sorted lexicographically by the rules of the alien language, so | |
| // from the given words we can conclude the following ordering among its characters: | |
| // 1. From "ba" and "bc", we can conclude that 'a' comes before 'c'. | |
| // 2. From "bc" and "ac", we can conclude that 'b' comes before 'a' | |
| // From the above two points, we can conclude that the correct character order is: "bac" | |
| // ["ba", "bc", "ac", "cab"] | |
| // ba | |
| // bc | |
| // ac | |
| // cab | |
| // ba | |
| // bc a comes before c | |
| // bc | |
| // ac b comes before a | |
| // ac | |
| // cab a comes before c | |
| // (a,c) | |
| // (b, a) | |
| // Example 2: | |
| // Input: Words: ["cab", "aaa", "aab"] | |
| // Output: cab | |
| // Explanation: From the given words we can conclude the following ordering among its characters: | |
| // 1. From "cab" and "aaa", we can conclude that 'c' comes before 'a'. | |
| // 2. From "aaa" and "aab", we can conclude that 'a' comes before 'b' | |
| // From the above two points, we can conclude that the correct character order is: "cab" | |
| // ["cab", "aaa", "aab"] | |
| // cab 0 | |
| // aaa 1 | |
| // aab 2 | |
| // (c,a) (a,b) | |
| // Example 3: | |
| // Input: Words: ["ywx", "wz", "xww", "xz", "zyy", "zwz"] | |
| // Output: ywxz | |
| // Explanation: From the given words we can conclude the following ordering among its characters: | |
| // 1. From "ywx" and "wz", we can conclude that 'y' comes before 'w'. | |
| // 2. From "wz" and "xww", we can conclude that 'w' comes before 'x'. | |
| // 3. From "xww" and "xz", we can conclude that 'w' comes before 'z' | |
| // 4. From "xz" and "zyy", we can conclude that 'x' comes before 'z' | |
| // 5. From "zyy" and "zwz", we can conclude that 'y' comes before 'w' | |
| // From the above five points, we can conclude that the correct character order is: "ywxz" | |
| // ["ywx", "wz", "xww", "xz", "zyy", "zwz"] | |
| // ywx | |
| // wz | |
| // xww | |
| // xz | |
| // zyy | |
| // zwz | |
| // (y,w) (w,x) (w,z) (x,z) | |
| public static String findOrder(String[] words) { | |
| if (words.length == 0) { return ""; } | |
| if (words.length == 1) { return words[0]; } | |
| Map<Character, Integer> inDegress = new HashMap(); | |
| Map<Character, List<Character>> graph = new HashMap(); | |
| for (String word : words) { | |
| word.chars().mapToObj(i -> (char)i).forEach(chr -> { | |
| inDegress.put(chr, 0); | |
| graph.put(chr, new ArrayList()); | |
| }); | |
| } | |
| for (int i=0; i<words.length-1; i=i+1) { | |
| String firstWord = words[i], secondWord = words[i+1]; | |
| for (int j=0; j<Math.min(firstWord.length(), secondWord.length()); j++) { | |
| if (firstWord.charAt(j) != secondWord.charAt(j)) { | |
| graph.get(firstWord.charAt(j)).add(secondWord.charAt(j)); | |
| inDegress.put(secondWord.charAt(j), inDegress.get(secondWord.charAt(j))+1); | |
| break; | |
| } | |
| } | |
| } | |
| StringBuilder result = new StringBuilder(); | |
| Queue<Character> sources = new LinkedList(); | |
| inDegress.entrySet().stream().filter(entry -> entry.getValue() == 0).forEach(entry -> sources.offer(entry.getKey())); | |
| while (!sources.isEmpty()) { | |
| char source = sources.poll(); | |
| result.append(source); | |
| List<Character> children = graph.get(source); | |
| for (char child : children) { | |
| inDegress.put(child, inDegress.get(child)-1); | |
| if (inDegress.get(child) == 0) { sources.offer(child); } | |
| } | |
| } | |
| return result.toString(); | |
| } | |
| public static void main(String[] args) { | |
| String result = findOrder(new String[] { "ba", "bc", "ac", "cab" }); | |
| System.out.println("Character order: " + result); | |
| result = findOrder(new String[] { "cab", "aaa", "aab" }); | |
| System.out.println("Character order: " + result); | |
| result = findOrder(new String[] { "ywx", "wz", "xww", "xz", "zyy", "zwz" }); | |
| System.out.println("Character order: " + result); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment