Python | LeetCode
Задача: 953. Verifying an Alien Dictionary
Сложность: hard
В инопланетном языке, как ни странно, тоже используются английские строчные буквы, но, возможно, в другом порядке. Порядок алфавита - это некоторая перестановка строчных букв. Учитывая последовательность слов, написанных на инопланетном языке, и порядок алфавита, верните true тогда и только тогда, когда данные слова отсортированы лексикографически на этом инопланетном языке.
Пример:
Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
👨💻 Алгоритм:
1⃣Создать словарь для хранения порядка каждой буквы в инопланетном языке.
Пройти по каждому слову и сравнить его с последующим словом.
2⃣Для каждого слова, сравнить буквы, используя созданный словарь порядка.
Если обнаружена пара слов, нарушающая порядок, вернуть false.
3⃣Если все слова отсортированы правильно, вернуть true.
😎 Решение:
def isAlienSorted(words, order):
order_map = {char: i for i, char in enumerate(order)}
def compare(word1, word2):
for c1, c2 in zip(word1, word2):
if order_map[c1] < order_map[c2]:
return True
elif order_map[c1] > order_map[c2]:
return False
return len(word1) <= len(word2)
for i in range(len(words) - 1):
if not compare(words[i], words[i + 1]):
return False
return True
Ставь 👍 и забирай 📚 Базу знаний
7 · 835 ·