Difficulty: Easy | Acceptance: 55.90% | Paid: No Topics: Array, Hash Table, String
In an alien language, surprisingly, they also use English lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.
Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographically in this alien language.
- Examples
- Constraints
- Direct Comparison
- Translation to English
Examples
Example 1
Input: words = [“hello”,“leetcode”], order = “hlabcdefgijkmnopqrstuvwxyz” Output: true Explanation: As ‘h’ comes before ‘l’ in this language, then the sequence is sorted.
Example 2
Input: words = [“word”,“world”,“row”], order = “worldabcefghijkmnpqstuvxyz” Output: false Explanation: As ‘d’ comes after ‘l’ in this language, then word[0] > word[1], hence the sequence is unsorted.
Example 3
Input: words = [“apple”,“app”], order = “abcdefghijklmnopqrstuvwxyz” Output: false Explanation: “app” should come before “apple” because “app” is a prefix of “apple”, but in normal dictionary order, shorter words come first.
Constraints
1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] consists of lowercase English letters.
order.length == 26
All characters in order are unique.
Direct Comparison
Intuition Create a mapping from each character to its position in the alien alphabet, then compare adjacent words character by character using this mapping.
Steps
- Create a hash map to store the index of each character in the order string
- Iterate through adjacent pairs of words
- For each pair, compare characters at the same position
- If characters differ, check if the first comes before the second in alien order
- If all characters match, ensure the first word is not longer than the second
from typing import List
class Solution:
def isAlienSorted(self, words: List[str], order: str) -> bool:
order_map = {char: idx for idx, char in enumerate(order)}
for i in range(len(words) - 1):
word1, word2 = words[i], words[i + 1]
for j in range(min(len(word1), len(word2))):
if word1[j] != word2[j]:
if order_map[word1[j]] > order_map[word2[j]]:
return False
break
else:
if len(word1) > len(word2):
return False
return True
Complexity
- Time: O(C) where C is the total number of characters across all words
- Space: O(1) for the order map (fixed size of 26)
- Notes: This is the most efficient approach with constant space for the mapping.
Translation to English
Intuition Translate each alien word to its English equivalent using the alien-to-English mapping, then use standard string comparison.
Steps
- Create a mapping from alien character to English character
- Translate each word by replacing each character with its English equivalent
- Compare adjacent translated words using standard lexicographic order
from typing import List
class Solution:
def isAlienSorted(self, words: List[str], order: str) -> bool:
alien_to_english = {order[i]: chr(ord('a') + i) for i in range(26)}
def translate(word: str) -> str:
return ''.join(alien_to_english[c] for c in word)
translated = [translate(word) for word in words]
return translated == sorted(translated)
Complexity
- Time: O(C log C) where C is the total number of characters, due to sorting
- Space: O(C) for storing translated words
- Notes: Less efficient than direct comparison due to sorting overhead, but conceptually simpler.