Practice/Meta/Leetcode 953. Verifying an Alien Dictionary

Leetcode 953. Verifying an Alien Dictionary

CodingOptional

Problem

You are given a list of words and a string representing a custom alphabetical ordering. Your task is to determine whether the words appear in sorted order according to this custom alphabet.

In the custom alphabet, each letter has a specific position that defines its ordering relative to other letters. For example, if the alphabet is "zyx...cba", then 'z' comes before 'y', which comes before 'x', and so on.

Words should be compared lexicographically using the custom alphabet. When comparing two words character by character, if one word is a prefix of another, the shorter word should come first.

Return true if the words are in sorted order according to the custom alphabet, and false otherwise.

Requirements

1. Compare each pair of adjacent words in the input list
2. Use the custom alphabet ordering instead of standard ASCII ordering
3. Handle cases where one word is a prefix of another (shorter word must come first)
4. Return true only if all adjacent pairs are in correct order

Constraints

• 1 ≤ words.length ≤ 100
• 1 ≤ words[i].length ≤ 20
• alphabet.length = 26
• All characters in words[i] and alphabet are lowercase English letters
• alphabet contains each letter exactly once

Examples

Example 1:

Input: words = ["hello", "interview", "zebra"], alphabet = "hijklmnopqrstuvwxyzabcdefg" Output: true Explanation: In this alphabet, 'h' < 'i' < 'z', so the words are in correct order.

Example 2:

Input: words = ["car", "cat", "bat"], alphabet = "abcdefghijklmnopqrstuvwxyz" Output: false Explanation: Using standard ordering, "car" and "cat" are fine, but "cat" should not come before "bat" since 'c' > 'b'.

Example 3:

Input: words = ["test", "testing"], alphabet = "abcdefghijklmnopqrstuvwxyz" Output: true Explanation: "test" is a prefix of "testing" and comes first, which is correct.