Problem statement

You have been given a sorted (lexical order) dictionary of an alien language.

Write a function that returns the order of characters as a string in the alien language. This dictionary will be given to you as an array of strings called ‘dictionary’, of size ‘N’.

Example

If the dictionary consists of the following words:-
[“caa”, “aaa”, “aab”], and ‘K’ is 3.

Then, the order of the alphabet is –
[‘c’, ‘a’, ‘b’]

Note

If the language consists of four letters, the four letters should be the starting four letters of the English language.

However, their order might differ in the alien language.

Test Cases

Sample Input 1 :
3 1
a aa aaa
Sample Output 1 :
true
Explanation For Sample Output 1 :
The words are ‘a’, ‘aa’, and ‘aaa’. Since the unique character here is ‘a’, the array to be returned will just be [‘a’].

The ‘true’ being printed signifies that the output returned by the function is valid.
Sample Input 2 :
3 3
caa aaa aab
Sample Output 2 :
true

Constraints

1 ≤ N ≤ 300
1 ≤ K ≤ 26
1 ≤ Length of words ≤ 50

Intuition

Let’s take the example [caa, aaa, aab]. In the alien dictionary, caa comes before aaa. WHY?

In a regular dictionary, aaa will come before caa because a is before c in lexicographic order. If we consider the same scenario for the alien dictionary, caa comes before aaa because c comes before a.

c  a a
!= = =
a  a a
c  a a
!= = =
a  a a
c  a a
!= = =
a  a a

Enter fullscreen mode Exit fullscreen mode

c comes before a.

Now consider the following two words [aaa, aab]. Keeping in mind the same logic, aaa comes before aab because a comes before b.

a a a
= = !=
a a b 
a a a
= = !=
a a b 
a a a
= = !=
a a b 

Enter fullscreen mode Exit fullscreen mode

a comes before b.

So we need to find the character ordering similar to abcde....z for the alien dictionary. One thing that comes to our mind is topological sorting, which will find the order in which certain operations will happen (here, the order of the alphabet in an alien dictionary). So we will build the graph and do Kahn’s algorithm or the DFS algorithm to find the topological sorting.

Algorithm

• Build the graph after comparing the words in the dictionary.
• We need to connect the nodes the very first moment we see a difference in the equality of characters.
• After we build the graph, find the indegree of the nodes.
• Do the BFS by adding all the nodes of indegree = 0 into the queue.
• Repeat the process for all indegree = 0 nodes for the neighbouring nodes. This is Kahn’s algorithm.

Time and Space Complexity

O(k + (dictionaryLength * maxOfWordLength)) graph build +
O(K + E) for indegree +
O(K + E) for bfs +
O(K) for final appending to the string

O(K + E) Space complexity

Code

<span>import</span> <span>java.util.*</span><span>;</span>
<span>public</span> <span>class</span> <span>Solution</span> <span>{</span>
    <span>public</span> <span>static</span> <span>String</span> <span>getAlienLanguage</span><span>(</span><span>String</span> <span>[]</span><span>dictionary</span><span>,</span> <span>int</span> <span>k</span><span>)</span> <span>{</span>
        <span>// Write your code here.</span>
        <span>if</span> <span>(</span><span>dictionary</span> <span>==</span> <span>null</span> <span>||</span> <span>dictionary</span><span>.</span><span>length</span> <span>==</span> <span>0</span><span>)</span> <span>{</span>
            <span>return</span> <span>""</span><span>;</span>
        <span>}</span>
        <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>graph</span> <span>=</span> <span>buildGraph</span><span>(</span><span>dictionary</span><span>,</span> <span>k</span><span>);</span>
        <span>StringBuilder</span> <span>alienWord</span> <span>=</span> <span>new</span> <span>StringBuilder</span><span>();</span>
        <span>int</span> <span>[]</span> <span>indegree</span> <span>=</span> <span>findIndegree</span><span>(</span><span>graph</span><span>,</span> <span>k</span><span>);</span> 
        <span>List</span><span><</span><span>Integer</span><span>></span> <span>orderOfAlphabets</span> <span>=</span> <span>findOrderOfAlphabets</span><span>(</span><span>graph</span><span>,</span> <span>k</span><span>,</span> <span>indegree</span><span>);</span>
        <span>for</span> <span>(</span><span>Integer</span> <span>alphabets</span> <span>:</span> <span>orderOfAlphabets</span><span>)</span> <span>{</span>
            <span>char</span> <span>respCharacter</span> <span>=</span> <span>(</span><span>char</span><span>)(</span><span>alphabets</span> <span>+</span> <span>'a'</span><span>);</span>
            <span>alienWord</span><span>.</span><span>append</span><span>(</span><span>respCharacter</span><span>);</span>
        <span>}</span>
        <span>return</span> <span>alienWord</span><span>.</span><span>toString</span><span>();</span>
    <span>}</span>
    <span>private</span> <span>static</span> <span>int</span> <span>[]</span> <span>findIndegree</span><span>(</span><span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>graph</span><span>,</span> <span>int</span> <span>k</span><span>)</span> <span>{</span>
        <span>int</span> <span>[]</span> <span>indegree</span> <span>=</span> <span>new</span> <span>int</span> <span>[</span><span>k</span><span>];</span>
        <span>for</span> <span>(</span><span>int</span> <span>letter</span> <span>=</span> <span>0</span><span>;</span> <span>letter</span> <span><</span> <span>k</span><span>;</span> <span>letter</span><span>++)</span> <span>{</span>
            <span>List</span><span><</span><span>Integer</span><span>></span> <span>children</span> <span>=</span> <span>graph</span><span>.</span><span>get</span><span>(</span><span>letter</span><span>);</span>
            <span>for</span> <span>(</span><span>Integer</span> <span>child</span> <span>:</span> <span>children</span><span>)</span> <span>{</span>
                <span>indegree</span><span>[</span><span>child</span><span>]++;</span>
            <span>}</span>
        <span>}</span>
        <span>return</span> <span>indegree</span><span>;</span>
    <span>}</span> 
    <span>private</span> <span>static</span> <span>List</span><span><</span><span>Integer</span><span>></span> <span>findOrderOfAlphabets</span><span>(</span><span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>graph</span><span>,</span> <span>int</span> <span>k</span><span>,</span> <span>int</span> <span>[]</span> <span>indegree</span><span>)</span> <span>{</span>
        <span>List</span><span><</span><span>Integer</span><span>></span> <span>orderOfAlphabets</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span>
        <span>Queue</span><span><</span><span>Integer</span><span>></span> <span>queue</span> <span>=</span> <span>new</span> <span>LinkedList</span><span><>();</span>
        <span>for</span> <span>(</span><span>int</span> <span>letter</span> <span>=</span> <span>0</span><span>;</span> <span>letter</span> <span><</span> <span>k</span><span>;</span> <span>letter</span><span>++)</span> <span>{</span>
            <span>if</span> <span>(</span><span>indegree</span><span>[</span><span>letter</span><span>]</span> <span>==</span> <span>0</span><span>)</span> <span>{</span>
                <span>queue</span><span>.</span><span>offer</span><span>(</span><span>letter</span><span>);</span>
            <span>}</span>
        <span>}</span>
        <span>while</span> <span>(!</span><span>queue</span><span>.</span><span>isEmpty</span><span>())</span> <span>{</span>
            <span>int</span> <span>topLetter</span> <span>=</span> <span>queue</span><span>.</span><span>poll</span><span>();</span>
            <span>orderOfAlphabets</span><span>.</span><span>add</span><span>(</span><span>topLetter</span><span>);</span>
            <span>List</span><span><</span><span>Integer</span><span>></span> <span>children</span> <span>=</span> <span>graph</span><span>.</span><span>get</span><span>(</span><span>topLetter</span><span>);</span>
            <span>for</span> <span>(</span><span>Integer</span> <span>child</span> <span>:</span> <span>children</span><span>)</span> <span>{</span>
                <span>indegree</span><span>[</span><span>child</span><span>]--;</span>
                <span>if</span> <span>(</span><span>indegree</span><span>[</span><span>child</span><span>]</span> <span>==</span> <span>0</span><span>)</span> <span>{</span>
                    <span>queue</span><span>.</span><span>offer</span><span>(</span><span>child</span><span>);</span>
                <span>}</span>
            <span>}</span>
        <span>}</span>
        <span>return</span> <span>orderOfAlphabets</span><span>;</span>
    <span>}</span>
    <span>private</span> <span>static</span> <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>buildGraph</span><span>(</span><span>String</span> <span>[]</span> <span>dictionary</span><span>,</span> <span>int</span> <span>k</span><span>)</span> <span>{</span>
        <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>graph</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span>
        <span>for</span> <span>(</span><span>int</span> <span>node</span> <span>=</span> <span>0</span><span>;</span> <span>node</span> <span><</span> <span>k</span><span>;</span> <span>node</span><span>++)</span> <span>{</span>
            <span>graph</span><span>.</span><span>add</span><span>(</span><span>new</span> <span>ArrayList</span><span><>());</span>
        <span>}</span>
        <span>int</span> <span>dictionaryLength</span> <span>=</span> <span>dictionary</span><span>.</span><span>length</span><span>;</span>
        <span>for</span> <span>(</span><span>int</span> <span>index</span> <span>=</span> <span>0</span><span>;</span> <span>index</span> <span>+</span> <span>1</span> <span><</span> <span>dictionaryLength</span><span>;</span> <span>index</span><span>++)</span> <span>{</span>
            <span>String</span> <span>word1</span> <span>=</span> <span>dictionary</span><span>[</span><span>index</span><span>];</span>
            <span>String</span> <span>word2</span> <span>=</span> <span>dictionary</span><span>[</span><span>index</span> <span>+</span> <span>1</span><span>];</span>
            <span>int</span> <span>diffIndex</span> <span>=</span> <span>-</span><span>1</span><span>;</span>
            <span>int</span> <span>word1Length</span> <span>=</span> <span>word1</span><span>.</span><span>length</span><span>();</span>
            <span>int</span> <span>word2Length</span> <span>=</span> <span>word2</span><span>.</span><span>length</span><span>();</span>
            <span>int</span> <span>maxLength</span> <span>=</span> <span>Math</span><span>.</span><span>min</span><span>(</span><span>word1Length</span><span>,</span> <span>word2Length</span><span>);</span>
            <span>int</span> <span>index1</span> <span>=</span> <span>0</span><span>;</span>
            <span>while</span> <span>(</span><span>index1</span> <span><</span> <span>maxLength</span><span>)</span> <span>{</span>
                <span>if</span> <span>(</span><span>word1</span><span>.</span><span>charAt</span><span>(</span><span>index1</span><span>)</span> <span>!=</span> <span>word2</span><span>.</span><span>charAt</span><span>(</span><span>index1</span><span>))</span> <span>{</span>
                    <span>diffIndex</span> <span>=</span> <span>index1</span><span>;</span>
                    <span>break</span><span>;</span>
                <span>}</span>
                <span>index1</span><span>++;</span>
            <span>}</span>
            <span>if</span> <span>(</span><span>diffIndex</span> <span>!=</span> <span>-</span><span>1</span><span>)</span> <span>{</span>
                <span>char</span> <span>diffAtWord1</span> <span>=</span> <span>word1</span><span>.</span><span>charAt</span><span>(</span><span>diffIndex</span><span>);</span>
                <span>char</span> <span>diffAtWord2</span> <span>=</span> <span>word2</span><span>.</span><span>charAt</span><span>(</span><span>diffIndex</span><span>);</span>
                <span>graph</span><span>.</span><span>get</span><span>(</span><span>diffAtWord1</span> <span>-</span> <span>'a'</span><span>).</span><span>add</span><span>(</span><span>diffAtWord2</span> <span>-</span> <span>'a'</span><span>);</span>
            <span>}</span>
        <span>}</span>
        <span>return</span> <span>graph</span><span>;</span>
    <span>}</span>
<span>}</span>
<span>import</span> <span>java.util.*</span><span>;</span>
<span>public</span> <span>class</span> <span>Solution</span> <span>{</span>
    <span>public</span> <span>static</span> <span>String</span> <span>getAlienLanguage</span><span>(</span><span>String</span> <span>[]</span><span>dictionary</span><span>,</span> <span>int</span> <span>k</span><span>)</span> <span>{</span>
        <span>// Write your code here.</span>
        <span>if</span> <span>(</span><span>dictionary</span> <span>==</span> <span>null</span> <span>||</span> <span>dictionary</span><span>.</span><span>length</span> <span>==</span> <span>0</span><span>)</span> <span>{</span>
            <span>return</span> <span>""</span><span>;</span>
        <span>}</span>
        <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>graph</span> <span>=</span> <span>buildGraph</span><span>(</span><span>dictionary</span><span>,</span> <span>k</span><span>);</span>
        <span>StringBuilder</span> <span>alienWord</span> <span>=</span> <span>new</span> <span>StringBuilder</span><span>();</span>
        <span>int</span> <span>[]</span> <span>indegree</span> <span>=</span> <span>findIndegree</span><span>(</span><span>graph</span><span>,</span> <span>k</span><span>);</span> 
        <span>List</span><span><</span><span>Integer</span><span>></span> <span>orderOfAlphabets</span> <span>=</span> <span>findOrderOfAlphabets</span><span>(</span><span>graph</span><span>,</span> <span>k</span><span>,</span> <span>indegree</span><span>);</span>
        <span>for</span> <span>(</span><span>Integer</span> <span>alphabets</span> <span>:</span> <span>orderOfAlphabets</span><span>)</span> <span>{</span>
            <span>char</span> <span>respCharacter</span> <span>=</span> <span>(</span><span>char</span><span>)(</span><span>alphabets</span> <span>+</span> <span>'a'</span><span>);</span>
            <span>alienWord</span><span>.</span><span>append</span><span>(</span><span>respCharacter</span><span>);</span>
        <span>}</span>
        <span>return</span> <span>alienWord</span><span>.</span><span>toString</span><span>();</span>
    <span>}</span>

    <span>private</span> <span>static</span> <span>int</span> <span>[]</span> <span>findIndegree</span><span>(</span><span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>graph</span><span>,</span> <span>int</span> <span>k</span><span>)</span> <span>{</span>
        <span>int</span> <span>[]</span> <span>indegree</span> <span>=</span> <span>new</span> <span>int</span> <span>[</span><span>k</span><span>];</span>
        <span>for</span> <span>(</span><span>int</span> <span>letter</span> <span>=</span> <span>0</span><span>;</span> <span>letter</span> <span><</span> <span>k</span><span>;</span> <span>letter</span><span>++)</span> <span>{</span>
            <span>List</span><span><</span><span>Integer</span><span>></span> <span>children</span> <span>=</span> <span>graph</span><span>.</span><span>get</span><span>(</span><span>letter</span><span>);</span>
            <span>for</span> <span>(</span><span>Integer</span> <span>child</span> <span>:</span> <span>children</span><span>)</span> <span>{</span>
                <span>indegree</span><span>[</span><span>child</span><span>]++;</span>
            <span>}</span>
        <span>}</span>
        <span>return</span> <span>indegree</span><span>;</span>
    <span>}</span> 

    <span>private</span> <span>static</span> <span>List</span><span><</span><span>Integer</span><span>></span> <span>findOrderOfAlphabets</span><span>(</span><span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>graph</span><span>,</span> <span>int</span> <span>k</span><span>,</span> <span>int</span> <span>[]</span> <span>indegree</span><span>)</span> <span>{</span>
        <span>List</span><span><</span><span>Integer</span><span>></span> <span>orderOfAlphabets</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span>
        <span>Queue</span><span><</span><span>Integer</span><span>></span> <span>queue</span> <span>=</span> <span>new</span> <span>LinkedList</span><span><>();</span>
        <span>for</span> <span>(</span><span>int</span> <span>letter</span> <span>=</span> <span>0</span><span>;</span> <span>letter</span> <span><</span> <span>k</span><span>;</span> <span>letter</span><span>++)</span> <span>{</span>
            <span>if</span> <span>(</span><span>indegree</span><span>[</span><span>letter</span><span>]</span> <span>==</span> <span>0</span><span>)</span> <span>{</span>
                <span>queue</span><span>.</span><span>offer</span><span>(</span><span>letter</span><span>);</span>
            <span>}</span>
        <span>}</span>
        <span>while</span> <span>(!</span><span>queue</span><span>.</span><span>isEmpty</span><span>())</span> <span>{</span>
            <span>int</span> <span>topLetter</span> <span>=</span> <span>queue</span><span>.</span><span>poll</span><span>();</span>
            <span>orderOfAlphabets</span><span>.</span><span>add</span><span>(</span><span>topLetter</span><span>);</span>
            <span>List</span><span><</span><span>Integer</span><span>></span> <span>children</span> <span>=</span> <span>graph</span><span>.</span><span>get</span><span>(</span><span>topLetter</span><span>);</span>
            <span>for</span> <span>(</span><span>Integer</span> <span>child</span> <span>:</span> <span>children</span><span>)</span> <span>{</span>
                <span>indegree</span><span>[</span><span>child</span><span>]--;</span>
                <span>if</span> <span>(</span><span>indegree</span><span>[</span><span>child</span><span>]</span> <span>==</span> <span>0</span><span>)</span> <span>{</span>
                    <span>queue</span><span>.</span><span>offer</span><span>(</span><span>child</span><span>);</span>
                <span>}</span>
            <span>}</span>
        <span>}</span>
        <span>return</span> <span>orderOfAlphabets</span><span>;</span>
    <span>}</span>

    <span>private</span> <span>static</span> <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>buildGraph</span><span>(</span><span>String</span> <span>[]</span> <span>dictionary</span><span>,</span> <span>int</span> <span>k</span><span>)</span> <span>{</span>
        <span>List</span><span><</span><span>List</span><span><</span><span>Integer</span><span>>></span> <span>graph</span> <span>=</span> <span>new</span> <span>ArrayList</span><span><>();</span>
        <span>for</span> <span>(</span><span>int</span> <span>node</span> <span>=</span> <span>0</span><span>;</span> <span>node</span> <span><</span> <span>k</span><span>;</span> <span>node</span><span>++)</span> <span>{</span>
            <span>graph</span><span>.</span><span>add</span><span>(</span><span>new</span> <span>ArrayList</span><span><>());</span>
        <span>}</span>
        <span>int</span> <span>dictionaryLength</span> <span>=</span> <span>dictionary</span><span>.</span><span>length</span><span>;</span>
        <span>for</span> <span>(</span><span>int</span> <span>index</span> <span>=</span> <span>0</span><span>;</span> <span>index</span> <span>+</span> <span>1</span> <span><</span> <span>dictionaryLength</span><span>;</span> <span>index</span><span>++)</span> <span>{</span>
            <span>String</span> <span>word1</span> <span>=</span> <span>dictionary</span><span>[</span><span>index</span><span>];</span>
            <span>String</span> <span>word2</span> <span>=</span> <span>dictionary</span><span>[</span><span>index</span> <span>+</span> <span>1</span><span>];</span>
            <span>int</span> <span>diffIndex</span> <span>=</span> <span>-</span><span>1</span><span>;</span>
            <span>int</span> <span>word1Length</span> <span>=</span> <span>word1</span><span>.</span><span>length</span><span>();</span>
            <span>int</span> <span>word2Length</span> <span>=</span> <span>word2</span><span>.</span><span>length</span><span>();</span>
            <span>int</span> <span>maxLength</span> <span>=</span> <span>Math</span><span>.</span><span>min</span><span>(</span><span>word1Length</span><span>,</span> <span>word2Length</span><span>);</span>
            <span>int</span> <span>index1</span> <span>=</span> <span>0</span><span>;</span>
            <span>while</span> <span>(</span><span>index1</span> <span><</span> <span>maxLength</span><span>)</span> <span>{</span>
                <span>if</span> <span>(</span><span>word1</span><span>.</span><span>charAt</span><span>(</span><span>index1</span><span>)</span> <span>!=</span> <span>word2</span><span>.</span><span>charAt</span><span>(</span><span>index1</span><span>))</span> <span>{</span>
                    <span>diffIndex</span> <span>=</span> <span>index1</span><span>;</span>
                    <span>break</span><span>;</span>
                <span>}</span>
                <span>index1</span><span>++;</span>
            <span>}</span>
            <span>if</span> <span>(</span><span>diffIndex</span> <span>!=</span> <span>-</span><span>1</span><span>)</span> <span>{</span>
                <span>char</span> <span>diffAtWord1</span> <span>=</span> <span>word1</span><span>.</span><span>charAt</span><span>(</span><span>diffIndex</span><span>);</span>
                <span>char</span> <span>diffAtWord2</span> <span>=</span> <span>word2</span><span>.</span><span>charAt</span><span>(</span><span>diffIndex</span><span>);</span>
                <span>graph</span><span>.</span><span>get</span><span>(</span><span>diffAtWord1</span> <span>-</span> <span>'a'</span><span>).</span><span>add</span><span>(</span><span>diffAtWord2</span> <span>-</span> <span>'a'</span><span>);</span>
            <span>}</span>
        <span>}</span>
        <span>return</span> <span>graph</span><span>;</span>
    <span>}</span>
<span>}</span>
import java.util.*;
public class Solution {
    public static String getAlienLanguage(String []dictionary, int k) {
        // Write your code here.
        if (dictionary == null || dictionary.length == 0) {
            return "";
        }
        List<List<Integer>> graph = buildGraph(dictionary, k);
        StringBuilder alienWord = new StringBuilder();
        int [] indegree = findIndegree(graph, k); 
        List<Integer> orderOfAlphabets = findOrderOfAlphabets(graph, k, indegree);
        for (Integer alphabets : orderOfAlphabets) {
            char respCharacter = (char)(alphabets + 'a');
            alienWord.append(respCharacter);
        }
        return alienWord.toString();
    }

    private static int [] findIndegree(List<List<Integer>> graph, int k) {
        int [] indegree = new int [k];
        for (int letter = 0; letter < k; letter++) {
            List<Integer> children = graph.get(letter);
            for (Integer child : children) {
                indegree[child]++;
            }
        }
        return indegree;
    } 

    private static List<Integer> findOrderOfAlphabets(List<List<Integer>> graph, int k, int [] indegree) {
        List<Integer> orderOfAlphabets = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int letter = 0; letter < k; letter++) {
            if (indegree[letter] == 0) {
                queue.offer(letter);
            }
        }
        while (!queue.isEmpty()) {
            int topLetter = queue.poll();
            orderOfAlphabets.add(topLetter);
            List<Integer> children = graph.get(topLetter);
            for (Integer child : children) {
                indegree[child]--;
                if (indegree[child] == 0) {
                    queue.offer(child);
                }
            }
        }
        return orderOfAlphabets;
    }

    private static List<List<Integer>> buildGraph(String [] dictionary, int k) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int node = 0; node < k; node++) {
            graph.add(new ArrayList<>());
        }
        int dictionaryLength = dictionary.length;
        for (int index = 0; index + 1 < dictionaryLength; index++) {
            String word1 = dictionary[index];
            String word2 = dictionary[index + 1];
            int diffIndex = -1;
            int word1Length = word1.length();
            int word2Length = word2.length();
            int maxLength = Math.min(word1Length, word2Length);
            int index1 = 0;
            while (index1 < maxLength) {
                if (word1.charAt(index1) != word2.charAt(index1)) {
                    diffIndex = index1;
                    break;
                }
                index1++;
            }
            if (diffIndex != -1) {
                char diffAtWord1 = word1.charAt(diffIndex);
                char diffAtWord2 = word2.charAt(diffIndex);
                graph.get(diffAtWord1 - 'a').add(diffAtWord2 - 'a');
            }
        }
        return graph;
    }
}

Enter fullscreen mode Exit fullscreen mode

原文链接：Alien Dictionary