{"id":2070,"date":"2024-02-01T13:00:00","date_gmt":"2024-02-01T13:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=2070"},"modified":"2024-03-02T07:52:32","modified_gmt":"2024-03-02T07:52:32","slug":"alien-dictionary-problem","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/alien-dictionary-problem\/","title":{"rendered":"Alien Dictionary Problem (C++, Java, Python)"},"content":{"rendered":"\n

The dictionary provides details about the order of alphabetical characters. For example, if abc, abd are two words where abd comes after abc, it means c is smaller than d. But if order is opposite this implies d is smaller than c. In this article, we will learn how to solve the Alien Dictionary problem.<\/p>\n\n\n\n

What is the Alien Dictionary Problem?<\/strong><\/h2>\n\n\n\n

In the Alien Dictionary problem, we are given an array containing words in the order it was written in a dictionary. This dictionary is not the same as our actual dictionary. You have to find the order of characters in that dictionary. <\/strong><\/p>\n\n\n\n

For example, array = [ \u201cacd\u201d, \u201cdc\u201d, \u201cca\u201d]. This means the actual order of letters is a, d, c.\u00a0<\/p>\n\n\n\n

\"Example\"\/<\/figure>\n\n\n\n
\"Example\"\/<\/figure>\n\n\n\n

Topological Sorting Approach<\/strong><\/h2>\n\n\n\n

In topological sorting<\/a>, we find out the order of the nodes. As in this case, we have to find out the order of the characters so we will assume characters a individual nodes, and the edges represent the relative order between them. <\/p>\n\n\n\n

We will first construct the graph by assuming each letter is an individual character and then construct the directed edges which denotes the direction in which we are moving. <\/strong>If we find out that the graph contains a cycle then topological sorting is not possible if not then return the ans.<\/p>\n\n\n\n

Let\u2019s understand this approach step by step:<\/p>\n\n\n\n

    \n
  1. First, create an adjacency list that stores the total number of unique characters in the array.<\/li>\n\n\n\n
  2. Now create the edges by comparing the characters of the adjacent words. Create the edges between the first characters which does not match.<\/li>\n\n\n\n
  3. Now find if the graph contains a cycle or not. If it contains cycle return the order is not possible to find.<\/li>\n\n\n\n
  4. If not find the topological order of the given graph and return the order.<\/li>\n<\/ol>\n\n\n\n

    Let\u2019s examine the code for the above process.<\/p>\n\n\n\n

    C++ Code<\/strong><\/h3>\n\n\n\n

    Here is how to implement topological sorting to solve Alien Dictionary problem:<\/p>\n\n\n\n

    #include<bits\/stdc++.h>\nusing namespace std;\n\nvector<int>cunt(26,0);\n\nvoid add_edge(vector<vector<int>>&list, char a, char b){\n    list[a-'a'].push_back(b-'a');\n}\n\nvoid dfs(vector<vector<int>>& list, vector<int>& temp, int curr, bool& flag)\n{\n\n\ttemp[curr] = 1;\n\n\tfor (int i = 0; i < list[curr].size(); i++) {\n\t\tint j = list[curr][i];\n\t\tif (temp[j] == 1) {\n\t\t\tflag = true;\n\t\t\treturn;\n\t\t}\n\t\telse if (temp[j] == 0) {\n\t\t\tdfs(list, temp, j, flag);\n\t\t}\n\t}\n\n\ttemp[curr] = 2;\n\treturn ;\n}\n\n\nbool is_cycle(vector<vector<int>>& list, vector<int>temp){\n    \n    bool flag = false;\n    \n    for(int i=0; i<26; i++){\n        if(list[i].size()){\n            if(temp[i] == 0) dfs(list, temp, i, flag);\n        }\n    }\n    \n    return flag;\n}\n\nvoid topological_sort_fun(vector<vector<int>>&list, int curr, vector<bool>& visited, stack<char>& st)\n{\n\tvisited[curr] = true;\n\t\n\tfor (int i = 0; i < list[curr].size(); i++) {\n\t\tint x = list[curr][i];\n\t\tif (visited[x] == false) {\n\t\t\ttopological_sort_fun(list, x, visited, st);\n\t\t}\n\t}\n\tst.push('a' + curr);\n\treturn;\n}\n\nstack<char> topological_sort(vector<vector<int>>& list){\n    \n    vector<bool>visited(26,false);\n    stack<char>st;\n    \n    for(int i=0;i<26;i++){\n        if(visited[i]==false && cunt[i]>0){\n            topological_sort_fun(list, i, visited, st);\n        }\n    }\n    \n    return st;\n    \n}\n\nvector<char> find_order(vector<string>& arr){\n    \/\/ first we find out how many unique characters are there\n    \n    for(int i=0;i<arr.size();i++){\n        for(int j=0;j<arr[i].size();j++){\n            cunt[arr[i][j]-'a']++;\n        }\n    }\n\n    \n    \/\/ finding the edges by looking at adjacent elements \n    \n    int n = arr.size();\n    vector<vector<int>>list(26);\n    for (int i = 0; i < n - 1; i++) {\n\t\n\t\tint j = 0;\n\t\tint sz_1 = arr[i].size();\n\t\tint sz_2 = arr[i+1].size();\n\t\t\n\t\twhile (j < sz_1 && j < sz_2) {  \n\t\t\tif (arr[i][j] != arr[i+1][j]) { \n\t\t\t\tadd_edge(list, arr[i][j], arr[i+1][j]);\t\n\t\t\t\tbreak;\n\t\t\t}\n\t\t\tj++;\n\t\t}\n\t}\n    \n    vector<int>temp(26, 0);\n    \n    \/\/ if graph consist of cycle or not\n    \n    if(is_cycle(list, temp)){\n        cout<<"No valid order is possible";\n        return {};\n    }\n    \n    \/\/ find the topologicalSort\n    stack<char>st = topological_sort(list);\n    \n    vector<char>res;\n    \n    while(st.size()){\n        char ch = st.top();\n        res.push_back(ch);\n        st.pop();\n    }\n\n    return res;\n}\n\nint main(){\n    vector<string>arr = {"bcd", "ddc", "dcb", "ab"};\n    vector<char>v = find_order(arr);\n    \n    for(int i=0;i<v.size();i++){\n        cout<<v[i]<<" ";\n    }\n    cout<<endl;\n    \n    return 0;\n}<\/pre><\/div>\n\n\n\n
    Java Code<\/strong><\/h3>\n\n\n\n
    Here is the Java program to do the same:<\/p>\n\n\n\n
    import java.util.*;\n\npublic class Main {\n    static int[] count = new int[26];\n\n    static void addEdge(ArrayList<ArrayList<Integer>> list, char a, char b) {\n        list.get(a - 'a').add(b - 'a');\n    }\n\n    static void dfs(ArrayList<ArrayList<Integer>> list, int[] temp, int curr, boolean[] flag) {\n        temp[curr] = 1;\n\n        for (int i = 0; i < list.get(curr).size(); i++) {\n            int j = list.get(curr).get(i);\n            if (temp[j] == 1) {\n                flag[0] = true;\n                return;\n            } else if (temp[j] == 0) {\n                dfs(list, temp, j, flag);\n            }\n        }\n\n        temp[curr] = 2;\n    }\n\n    static boolean isCycle(ArrayList<ArrayList<Integer>> list, int[] temp) {\n        boolean[] flag = {false};\n\n        for (int i = 0; i < 26; i++) {\n            if (!list.get(i).isEmpty() && temp[i] == 0) {\n                dfs(list, temp, i, flag);\n            }\n        }\n\n        return flag[0];\n    }\n\n    static void topologicalSortFun(ArrayList<ArrayList<Integer>> list, int curr, boolean[] visited, Stack<Character> st) {\n        visited[curr] = true;\n\n        for (int i = 0; i < list.get(curr).size(); i++) {\n            int x = list.get(curr).get(i);\n            if (!visited[x]) {\n                topologicalSortFun(list, x, visited, st);\n            }\n        }\n        st.push((char)('a' + curr));\n    }\n\n    static Stack<Character> topologicalSort(ArrayList<ArrayList<Integer>> list) {\n        boolean[] visited = new boolean[26];\n        Stack<Character> st = new Stack<>();\n\n        for (int i = 0; i < 26; i++) {\n            if (!visited[i] && count[i] > 0) {\n                topologicalSortFun(list, i, visited, st);\n            }\n        }\n\n        return st;\n    }\n\n    static ArrayList<Character> findOrder(ArrayList<String> arr) {\n        for (String s : arr) {\n            for (char c : s.toCharArray()) {\n                count[c - 'a']++;\n            }\n        }\n\n        int n = arr.size();\n        ArrayList<ArrayList<Integer>> list = new ArrayList<>();\n        for (int i = 0; i < 26; i++) {\n            list.add(new ArrayList<>());\n        }\n\n        for (int i = 0; i < n - 1; i++) {\n            int j = 0;\n            int sz_1 = arr.get(i).length();\n            int sz_2 = arr.get(i + 1).length();\n            while (j < sz_1 && j < sz_2) {\n                if (arr.get(i).charAt(j) != arr.get(i + 1).charAt(j)) {\n                    addEdge(list, arr.get(i).charAt(j), arr.get(i + 1).charAt(j));\n                    break;\n                }\n                j++;\n            }\n        }\n\n        int[] temp = new int[26];\n        if (isCycle(list, temp)) {\n            System.out.println("No valid order is possible");\n            return new ArrayList<>();\n        }\n\n        Stack<Character> st = topologicalSort(list);\n        ArrayList<Character> res = new ArrayList<>();\n\n        while (!st.isEmpty()) {\n            char ch = st.pop();\n            res.add(ch);\n        }\n\n        return res;\n    }\n\n    public static void main(String[] args) {\n        ArrayList<String> arr = new ArrayList<>(Arrays.asList("bcd", "ddc", "dcb", "ab"));\n        ArrayList<Character> v = findOrder(arr);\n\n        for (char c : v) {\n            System.out.print(c + " ");\n        }\n        System.out.println();\n    }\n}<\/pre><\/div>\n\n\n\n
    Python Code<\/strong><\/h3>\n\n\n\n
    Python can also be used to solve this leetcode problem:<\/p>\n\n\n\n
    count = [0] * 26\n\ndef add_edge(list, a, b):\n    list[ord(a) - ord('a')].append(ord(b) - ord('a'))\n\ndef dfs(list, temp, curr, flag):\n    temp[curr] = 1\n\n    for i in range(len(list[curr])):\n        j = list[curr][i]\n        if temp[j] == 1:\n            flag[0] = True\n            return\n        elif temp[j] == 0:\n            dfs(list, temp, j, flag)\n\n    temp[curr] = 2\n\ndef is_cycle(list, temp):\n    flag = [False]\n\n    for i in range(26):\n        if list[i] and temp[i] == 0:\n            dfs(list, temp, i, flag)\n\n    return flag[0]\n\ndef topological_sort_fun(list, curr, visited, st):\n    visited[curr] = True\n\n    for i in range(len(list[curr])):\n        x = list[curr][i]\n        if not visited[x]:\n            topological_sort_fun(list, x, visited, st)\n    st.append(chr(ord('a') + curr))\n\ndef topological_sort(list):\n    visited = [False] * 26\n    st = []\n\n    for i in range(26):\n        if not visited[i] and count[i] > 0:\n            topological_sort_fun(list, i, visited, st)\n\n    return st\n\ndef find_order(arr):\n    global count\n    for s in arr:\n        for c in s:\n            count[ord(c) - ord('a')] += 1\n\n    n = len(arr)\n    list = [[] for _ in range(26)]\n\n    for i in range(n - 1):\n        j = 0\n        sz_1 = len(arr[i])\n        sz_2 = len(arr[i + 1])\n        while j < sz_1 and j < sz_2:\n            if arr[i][j] != arr[i + 1][j]:\n                add_edge(list, arr[i][j], arr[i + 1][j])\n                break\n            j += 1\n\n    temp = [0] * 26\n    if is_cycle(list, temp):\n        print("No valid order is possible")\n        return []\n\n    st = topological_sort(list)\n    res = []\n\n    while st:\n        ch = st.pop()\n        res.append(ch)\n\n    return res\n\nif __name__ == "__main__":\n    arr = ["bcd", "ddc", "dcb", "ab"]\n    v = find_order(arr)\n\n    for c in v:\n        print(c, end=" ")\n    print()<\/pre><\/div>\n\n\n\n
    Output: <\/strong><\/p>\n\n\n\n
    b d c a <\/code><\/pre>\n\n\n\n
    Complexity Analysis<\/strong><\/h3>\n\n\n\n
    The time complexity for implementing topological sorting to solve the Alien Dictionary problem is O(n + k), where n is the total number of words in the array and k is the total unique characters in the array. <\/strong>As we are making an adjacency list having a node equal to k. <\/p>\n\n\n\n
    The space complexity for the above code is O(n + k).<\/strong> As there are total n different words and we are comparing each adjacent word and based on this we will push that character into one of the nodes.<\/p>\n\n\n\n
    Conclusion<\/strong><\/h2>\n\n\n\n
    This article helps us to understand the topological sort in more depth to verify an Alien Dictionary. We find out how we can apply topological sort when we have to find the order of nodes in the graph. <\/p>\n","protected":false},"excerpt":{"rendered":"
    Understand what is the Alien Dictionary Problem and how to solve it using the Topological Sort approach.<\/p>\n","protected":false},"author":14,"featured_media":2072,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-2070","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2070","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=2070"}],"version-history":[{"count":3,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2070\/revisions"}],"predecessor-version":[{"id":2120,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2070\/revisions\/2120"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/2072"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=2070"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=2070"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=2070"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}