Katkat
Back

Validate Sorted Order Under a Custom Alphabet

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to define custom comparison logic using a lookup table and verify if a list of strings adheres to a non-standard lexicographical ordering.

Problem Statement

Given an array of words and a string representing a custom alphabet, determine if the words are sorted lexicographically according to this new alphabet order.

An alphabet is a string of 26 unique characters representing the order of precedence. For example, if the alphabet is "zyx...a", then 'z' comes before 'y'.

Write a function: def is_sorted(words: list[str], order: str) -> bool:

Rules

  1. Return True if the words are sorted lexicographically according to the order string, otherwise False.
  2. A word is considered "less than" another if at the first differing position, the character in the first word appears earlier in the custom alphabet.
  3. If one word is a prefix of another, the shorter word must come first.

Examples

Example 1: Input: words = ["hello", "leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz" Output: True Explanation: 'h' comes before 'l' in the custom order, so "hello" "world", which violates the order.

Constraints

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • order.length == 26
  • All strings consist of lowercase English letters.

Hints

Hint 1

Create a mapping (e.g., a dictionary or array) where each character in the custom alphabet is assigned an integer index representing its rank.

Hint 2

Compare adjacent words in the list one pair at a time; if any pair violates the order, the entire list is not sorted.

Hint 3

When comparing two words, check character by character; handle the edge case where one word is a prefix of the other by checking their lengths.

Follow-up questions

  • What is the time and space complexity of your solution in terms of total characters N and alphabet size K?
  • How would you modify your solution if the input contained uppercase characters as well?
  • If the input list of words was massive and stored on disk, how would you check for sorted order without loading all words into memory?