Alien Dictionary LeetCode Solution

Table of Contents

Problem Statement

Alien Dictionary LeetCode Solution – There is a new alien language that uses the English alphabet. However, the order among the letters is unknown to you.

You are given a list of strings words from the alien language’s dictionary, where the strings in words are sorted lexicographically by the rules of this new language.

Return a string of the unique letters in the new alien language sorted in lexicographically increasing order by the new language’s rules. If there is no solution, return "". If there are multiple solutions, return any of them.

A string s is lexicographically smaller than a string t if at the first letter where they differ, the letter in s comes before the letter in t in the alien language. If the first min(s.length, t.length) letters are the same, then s is smaller if and only if s.length < t.length.

Example

Test Case 1:

Input:

words = [“wrt”, “wrf”, “er”, “ett”, “rftt”]

Output:

“wertf”

Test Case 2:

Input:

words = [“z”, “x”, “z”]

Output:

“”

Explanation

i) In the first test case, “wertf” is the correct string possible.

ii) In the second test case, the order is invalid, so return “”.

Approach:

Let’s understand the problem statement first

words are sorted lexicographically which means if W[i] appears in the dictionary before W[j] for i < j.
Please note that individual words are not sorted. If abcde appears before abpqrst that doesn’t mean b appears before a.

Main things to note:

1. In a dictionary of words, for any two consecutive words, the order is decided by looking at the first uncommon char.

2. The chars following the uncommon char can’t be relied upon to conclude in any order. The reason being the order between the words was decided purely based on the first mismatching char, so any char after that is only there to constitute the complete word.

3. The consecutive chars appearing in any word has nothing to do with the order but they are there just to form the complete word.

Approach:

1. Create Graph: Using the above points, we iterate through consecutive word pairs and try to create edges.

2. Topological Sort: This can be done using DFS or BFS. I decided to go with BFS here

Edge cases

["abc", "ab"] – it’s not a valid dictionary, if W[i] < W[j] in the dictionary then W[j] can not be prefix of W[i]. so in this case simply return an empty string.
["a", "b", "a"] – here in this input, a < b and b < a, which is a cycle. a dictionary can not contain a cycle.

Code for Alien Dictionary

C++ Program

class Solution {
public:
    // Finds the topological order of a directed Acyclic graph
    string topologicalSortBFS(unordered_map<char, unordered_set<char>> &g) {
        unordered_map<char, int> indegree;
        queue<char> q;
        // topological order
        string order;
        
        // Compute the indegree of each node
        for(auto u: g) {
            char src = u.first;
            for(auto neighbor: g[src]) 
                ++indegree[neighbor];
        }
        
        // if current has no dependency, add and mark as visited
        for(auto u: g) {
            char src = u.first;
            if(!indegree[src]) {
                q.emplace(src);
            }
        }
        // BFS traversal wrt to indegree of each node
        while(!q.empty()) {
            auto curr = q.front();
            q.pop();
            order += curr;
            
            // reduce the indegree of its neighbors
            for(auto neighbor: g[curr]) {
                --indegree[neighbor];
                if(!indegree[neighbor]) 
                    q.emplace(neighbor);
            }
        }
        return order.size() < g.size() ? "" : order;
    }
    
    string alienOrder(vector<string>& words) {
        // create a graph
        // To create a graph using the lexographic order,
        // we need to look at the consecutive word pairs and 
        // within the common length check for diff chars at the same
        // index position, each unequal pair is a directed edge coming
        // from words[i][j] to words[i+1][j]
        unordered_map<char, unordered_set<char>> g;
        // initialize the graph with nodes req
        for(auto &word: words)
            for(char &ch: word)
                if(!g.count(ch))
                    g[ch] = unordered_set<char>();
        
        // Imp: Add all the seen chars to graph even with 0 edges
        for(int w = 0; w + 1 < words.size(); w++) {
            int common_len = min(words[w].size(), words[w+1].size());
            // check if the lexographic order is being followed or not
            // P.S I dont think this case is even valid acc to problem description
            // Eg: ["abc", "ab"] -> Invalid
            if(words[w+1].size() < words[w].size() 
               && words[w].substr(0, common_len) == words[w+1])
                return "";
            
            for(int i = 0; i < common_len; i++) {
                // prevent self loop
                char src = words[w][i], dst = words[w+1][i];
                // If current pos has diff chars, then make an edge and
                // break since, the current word ordering was due this positional char
                // change and anything beyond this might not follow actual order.
                if(src != dst) {
                    g[src].emplace(dst);
                    break;
                }
            }
        }
        
        string order = topologicalSortBFS(g);
        return order;
    }
};

Java Program

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> dict = new HashMap<>();
        Map<Character, Boolean> visited = new HashMap<>();
        
    // add character to visited map, mark all of them as unvisited
        for (String str: words) {
            for (char ch: str.toCharArray()) {
                visited.put(ch, false);
            }
        }
    
    // 
        for (int i = 0; i < words.length-1; i++) {
            if(!fillDict(dict, words[i], words[i+1])) {
                // invalid input, ex:- ab,abc is not a valid dictionary word
                return "";
            }
        }

        StringBuilder builder = new StringBuilder();
        for (char ch: visited.keySet()) {
            if (!visited.get(ch)) {
                // do the topological sorting from each unvisited dictionary character
                if (!topological(dict, ch, visited, new HashSet<>(), builder)) {
                    // loop detected. topological sort can not be performed in graph with cycle
                    return "";
                }
            }
        }
        return builder.reverse().toString();
    }
    
    private boolean topological(Map<Character, Set<Character>> dict, char ch,
                               Map<Character, Boolean> visited,
                               Set<Character> dfsStack, StringBuilder builder) {
        if (dfsStack.contains(ch)) {
            // oops!! loop detected
            return false;
        }
        if (visited.get(ch)) {
            return true;
        }
        visited.put(ch, true);
        dfsStack.add(ch);
        for (char c : dict.getOrDefault(ch, new HashSet<>())) {
            if (!topological(dict, c, visited, dfsStack, builder)) {
                return false;
            }
        }
        builder.append(ch);
        dfsStack.remove(ch);
        return true;
    }
    
    private boolean fillDict(Map<Character, Set<Character>> dict, String a, String b) {
        for (int i = 0; i < Math.min(a.length(), b.length()); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                dict.computeIfAbsent(a.charAt(i), x -> new HashSet<>()).add(b.charAt(i));
                return true;
            }
        }
        // minimum word is prefix of larger word, make sure word with less length comes before larger word
        // why? because if one string is prefix of another then prefix must come before string for example,
        // we are here becasue a,b = "abc" or "ab", since a is lexicographically smaller than b then a must
        // be "ab" because "abc" can never come before "ab".
        return a.length() <= b.length(); 
    }
}

Complexity Analysis for Alien Dictionary LeetCode Solution

Time Complexity: O(V + E)

Space Complexity: O(V + E) for graph creation