Show problems as
Classic problem #953EasyArrayHash TableString

Verifying an Alien Dictionary

Real-world version: Catalogue Order Under a Custom Glyph Sequence
Tracked in this browser only
Read Verifying an Alien Dictionary on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A typesetting house keeps its catalogue sorted by a house glyph sequence rather than by the usual alphabet. The string order lists all 26 lowercase letters exactly once, from the earliest glyph to the latest.

Under that sequence, one entry comes before another when, at the first position where the two entries carry different letters, this entry's letter appears earlier in order. If one entry is a prefix of the other, the shorter one comes first. Two identical entries may sit next to each other in either arrangement.

Given the catalogue words in the order it is printed, return true if no entry comes before the entry ahead of it, and false otherwise.

Examples

Example 1

Input
words = ["hut", "hub", "bore"], order = "hqtbmzadcefgijklnoprsuvwxy"
Output
true

In this glyph sequence t comes before b, so "hut" precedes "hub", and h comes before b, so "hub" precedes "bore".

Example 2

Input
words = ["apple", "app"], order = "abcdefghijklmnopqrstuvwxyz"
Output
false

The glyph sequence is the ordinary alphabet here. "app" is a prefix of "apple", so the shorter entry has to be printed first, and it is not.

Example 3

Input
words = ["drum", "drums", "drop"], order = "abcdefghijklmnopqrstuvwxyz"
Output
false

"drum" before "drums" is fine by the prefix rule, but "drums" and "drop" first differ at position 2, where u comes after o.

Constraints

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 20
  • order.length == 26
  • order contains each lowercase English letter exactly once.
  • words[i] consists of lowercase English letters.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def is_alien_sorted(words: list[str], order: str) -> bool:
Java
public boolean isAlienSorted(String[] words, String order)

More on the same topics