Alien Dictionary

hardFREEGraphsBlind 75

Given a sorted list of words in an alien language, derive the character ordering. Output the characters in order. If invalid (cycle), output empty string. If multiple valid orderings, output any one.

Example

Input

wrt,wrf,er,ett,rftt

Output

wertf

Reasoning

The input list of words is compared pairwise to derive the character ordering, starting with wrt and wrf, which implies t comes after f.
Comparing wrt and er implies w comes before e, and er and ett implies r comes before t.
The relationships derived from these comparisons are combined to form a graph, where each character is a node and the edges represent the ordering.
A topological sort is performed on this graph, resulting in the ordering w-e-r-t-f, which is output as the string wertf.

Constraints

1 <= len(words) <= 100
1 <= len(words[i]) <= 100
All characters are lowercase English letters

Learn this in

Advanced GraphsDSA Study Plan

More from Blind 75

Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard Remove Nth Node From End of Listmedium

Concept primer

Background Knowledge

The "Alien Dictionary" problem involves graph theory, specifically directed acyclic graphs (DAGs) and topological sorting. A DAG is a graph with directed edges and no cycles, meaning it's impossible to start at a node and follow the edges to return to the same node. Topological sorting is the process of ordering the nodes in a DAG such that for every edge (u, v), node u comes before node v in the ordering. This concept is crucial in solving the "Alien Dictionary" problem, as we need to derive the character ordering from a sorted list of words.

In the context of the problem, each character in the alien language can be represented as a node in the graph. The directed edges between nodes represent the ordering of characters, where an edge from node A to node B indicates that character A comes before character B in the ordering. The goal is to perform a topological sort on this graph to obtain a valid character ordering. If the graph contains a cycle, it means there's no valid ordering, and we should output an empty string.

To tackle this problem, it's essential to understand the basics of graph traversal and cycle detection. Graph traversal algorithms, such as depth-first search (DFS) and breadth-first search (BFS), can be used to explore the graph and detect cycles. Additionally, understanding the concept of in-degree (the number of edges entering a node) and out-degree (the number of edges leaving a node) can help in identifying nodes with no incoming edges, which can be used as starting points for the topological sort.

Algorithm/Approach

The general approach to solving this type of problem involves using a graph-based algorithm, specifically a topological sorting algorithm. The algorithm should be able to handle directed edges and detect cycles in the graph. Some common algorithms for topological sorting include Kahn's algorithm and DFS-based algorithms. These algorithms typically involve the following steps: building the graph, calculating in-degrees, and performing the topological sort.

Step-by-Step Strategy

To implement the solution, follow these steps:

Create a graph data structure to represent the alien language characters and their ordering.
Iterate through the sorted list of words to build the graph and calculate the in-degrees of each node.
Identify nodes with no incoming edges (in-degree 0) as starting points for the topological sort.
Perform the topological sort using a graph traversal algorithm, such as DFS or BFS.
If a cycle is detected during the traversal, return an empty string.
Otherwise, return the sorted list of characters.

Common Pitfalls

When implementing the solution, watch out for the following:

Incorrectly handling edge cases, such as an empty input list or a list with a single word.
Failing to detect cycles in the graph, which can lead to incorrect results.
Not properly calculating in-degrees or identifying starting points for the topological sort.
Using an inefficient graph traversal algorithm, which can lead to performance issues.

Time & Space Complexity

The expected time complexity for this problem is O(N * M), where N is the number of words in the input list and M is the maximum length of a word. The space complexity is O(N * M), as we need to store the graph and in-degrees for each node. However, the actual complexity may vary depending on the specific implementation and graph traversal algorithm used.

solution.py

Python 3.13

Test results