cswork / libraryOpen practice workspace

Coding questions · Meta

Check and infer custom alphabet

This question evaluates understanding of string comparison under a custom lexicographic order, the ability to validate whether a list of words is sorted according to that order, and the ability to infer a consistent character precedence from an ordered list.

You are working with an unknown language that uses a custom alphabetical order, such as ['a', 'd', 'c', 'b', ...].

Implement the following:

  1. Check sorted order: Given a custom alphabet order and an array of strings, determine whether the strings are sorted in nondecreasing lexicographic order under that alphabet.
  2. Follow-up: Given an array of strings that is already sorted according to an unknown custom alphabet, infer one possible alphabet order that is consistent with the given list. If no valid order exists, return that it is impossible.

Assumptions:

  • All strings consist of lowercase letters.
  • Lexicographic comparison is based on the first differing character.
  • If one word is a prefix of another, the shorter word must come first.
  • In the follow-up, if multiple valid alphabet orders exist, returning any one of them is acceptable.

Check Sorted Order Under Custom Alphabet

Return whether words are nondecreasing under the supplied custom alphabet.

Examples

Example 1

Input: ('hlabcdefgijkmnopqrstuvwxyz', ['hello','leetcode'])
Output: True

Explanation: Alien dictionary example.

Example 2

Input: ('abcdefghijklmnopqrstuvwxyz', ['apple','app'])
Output: False

Explanation: Prefix violation.

Hints

  1. Use deterministic tie-breaking for prompts with multiple valid outputs.
  2. For design-style APIs, simulate operations with explicit inputs.

Infer One Consistent Custom Alphabet

Given sorted words, infer one possible character order or return impossible.

Examples

Example 1

Input: (['wrt','wrf','er','ett','rftt'],)
Output: 'wertf'

Explanation: Classic ordering.

Example 2

Input: (['abc','ab'],)
Output: 'impossible'

Explanation: Invalid prefix.

Hints

  1. Use deterministic tie-breaking for prompts with multiple valid outputs.
  2. For design-style APIs, simulate operations with explicit inputs.