Katkat
Back

Verify Ordering Under a Scrambled Alphabet

TruefoundrySoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests string manipulation, hash map usage for indexing, and the ability to compare two strings based on custom character priority.

Problem Statement

Given a list of strings words and a string order representing a custom lexicographical alphabet (where each character in order is unique and defines the priority of characters), determine if the given words list is sorted in non-decreasing order.

Function Signature

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

Constraints

  • 1 <= len(words) <= 1000
  • 1 <= len(words[i]) <= 1000
  • len(order) == 26 (assuming lowercase English letters)

Examples

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

Example 2: Input: words = ["word", "world", "row"], order = "worldabcefghijkmnpqstuvxyz" Output: False Explanation: In "word" and "world", the first three characters are equal. The fourth characters are 'd' and 'l'. Since 'l' appears before 'd' in the custom order, the list is not sorted.

Edge Cases

  • A word being a prefix of another word (e.g., ["apple", "app"] is not sorted).
  • Empty lists or single-word lists.
  • Strings with identical characters.

Hints

Hint 1

Create a mapping (hash table or array) that stores the rank (index) of each character based on the input `order` string for constant time lookups.

Hint 2

Compare adjacent words in the list one by one; if any pair is out of order, immediately return False.

Hint 3

When comparing two words, iterate character by character until you find a difference or reach the end of the shorter word; handle the prefix case where the longer word must come after the shorter word.

Follow-up questions

  • How would you modify your solution if the input `order` contained a subset of characters, meaning some characters are not defined?
  • What is the time complexity of your solution in terms of total characters in all words (N) and the alphabet size (A)?
  • How would you optimize the solution if you had to perform this check repeatedly for millions of words?