How should I practice Alien Dictionary?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Intuit online assessment problems in FastPrep.

Is Alien Dictionary associated with Intuit?

FastPrep tags this as a Intuit online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Graph

Alien Dictionary

Learn this problem

● Hard

IntuitINTERNOA

Problem statement

You are given an array words sorted according to an unknown alphabet. Derive an ordering of every distinct lowercase letter that appears in words.

For each adjacent pair of words, the first position where their letters differ establishes which letter must come first. If one word is a prefix of the other, the shorter word must come first.

Return the lexicographically smallest valid ordering. Return an empty string when the ordering is impossible because of an invalid prefix or a cycle.

Function

alienOrder(words: String[]) → String

Examples

Example 1

words = ["wrt","wrf","er","ett","rftt"]return = "wertf"

The adjacent pairs imply t < f, w < e, r < t, and e < r, so the ordering is wertf.

Example 2

words = ["za","zb","ca","cb"]return = "abzc"

The constraints are a < b and z < c. Several topological orders are valid; abzc is lexicographically smallest.

Example 3

words = ["abc","ab"]return = ""

The longer word appears before its exact prefix, so no alphabet can make the list sorted.

Constraints

1 <= words.length <= 500.
1 <= words[i].length <= 100.
The total number of letters across all words is at most 10000.
Every word contains only lowercase English letters.