How should I practice Alien Dictionary?

Start by reading the full statement, solve the visible examples, then compare the pattern against related ByteDance phone screen problems in FastPrep.

Is Alien Dictionary associated with ByteDance?

FastPrep tags this as a ByteDance phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Graph

Alien Dictionary

Learn this problem

● Hard

ByteDanceNEW GRADPHONE SCREEN

Problem statement

An alien language uses the lowercase English letters, but their order is unknown. You are given an array words that is intended to be sorted from smallest to largest according to that alien alphabet.

Return the lexicographically smallest ordering of every distinct character that makes the dictionary order valid. If no such ordering exists, return the empty string.

For two different words, compare characters from left to right. At the first position where they differ, the character in the earlier word must come before the character in the later word. If all compared characters match, the shorter word must come first.

Each precedence relationship must be counted only once, even if multiple adjacent word pairs imply it.

Function

alienOrder(words: String[]) → String

Examples

Example 1

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

The adjacent pairs establish w < e, e < r, r < t, and t < f, so the only valid order is wertf.

Example 2

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

The constraints are a < b and z < c. Several orders are valid, and abzc is the lexicographically smallest one.

Example 3

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

A longer word cannot appear before its exact prefix in a sorted dictionary, so no valid alphabet exists.

Constraints

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