Verifying an Alien Dictionary
Verifying an Alien Dictionary is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Hashing - Frequency Map / Counting subpattern.
Problem statement
Implement Solution.isAlienSorted(words, order) to determine whether the list words is sorted according to an alien alphabet. The string order gives the complete character ranking: a character appearing earlier in order is considered smaller than one appearing later.
Compare words lexicographically using this ranking. For two words, the first position where their characters differ determines their order. If one word is a prefix of the other, the shorter word must come first. Equal words are allowed.
Return true if every consecutive pair in words follows these rules; otherwise, return false.
Example 1:
Input: words = ["mango","map","mat"], order = "abcdefghijklmnopqrstuvwxyz" Output: true Explanation: The words are in ordinary alphabetical order: "mango" comes before "map", and "map" comes before "mat" at their first differing character.
Example 2:
Input: words = ["zone","zoo"], order = "zyxwvutsrqponmlkjihgfedcba" Output: false Explanation: After the shared prefix z, the reversed alphabet ranks o before n, so zoo should come before zone.
Example 3:
Input: words = ["cabin","cabinet"], order = "abcdefghijklmnopqrstuvwxyz" Output: true Explanation: cabin is a prefix of cabinet, and the shorter word correctly appears first.
Constraints:
- 1 <= words.length <= 100 - 1 <= words[i].length <= 20 - words[i] contains only lowercase English letters - order.length = 26 - order is a permutation of the 26 lowercase English letters
Topics and companies
Topics: String, Hash Table, Array, Two Pointers.
How to practise Verifying an Alien Dictionary on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(sum of the lengths of the words) in the worst case. time and O(1), using a fixed-size 26-element ranking array. space.
Open Verifying an Alien Dictionary in the code editor, or read the Verifying an Alien Dictionary editorial for a worked solution with its approach and complexity analysis.
Where Verifying an Alien Dictionary sits in the DSA pattern sheet
- Array/Matrix Manipulation Patterns pattern guide
- Hashing - Frequency Map / Counting subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Verifying an Alien Dictionary
Other problems that use the same Hashing - Frequency Map / Counting and Array/Matrix Manipulation Patterns techniques:
- Find the Town Judge — Easy, same subpattern
- Group Anagrams — Medium, same subpattern
- Majority Element — Easy, same subpattern
- Majority Element II — Medium, same subpattern
- Subarray Sum Equals K — Medium, same subpattern
- Two Sum — Easy, same subpattern