Описание
Удивительно, но на чужом языке они также используют строчные английские буквы, но, возможно, в другом order
. order
алфавита - это некоторая перестановка строчных букв.
Учитывая последовательность words
, написанных на чужом языке, и order
алфавита, вернуть true
тогда и только тогда, когда данные words
лексикографически отсортированы на этом чужом языке.
Пример 1:
Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz" Output: true Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.
Пример 2:
Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz" Output: false Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.
Пример 3:
Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz" Output: false Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info).
Ограничения:
1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
- Все символы в
words[i]
иorder
- это строчные буквы английского алфавита.
Решение
Прежде всего, давайте выясним, что такое лексикографический порядок - вики. Что нам действительно нужно знать о лексикографическом порядке для решения этой задачи:
- Если два слова имеют одинаковую первую букву, мы сравниваем вторую. Если вторые буквы совпадают, сравниваем третью и так далее. Наконец, одно слово предшествует другому, если первая отличающаяся буква стоит перед соответствующей буквой.
- Если два слова идентичны до длины более короткого слова, более короткое слово идет первым.
Другими словами - javascript.info:
- Сравните первый символ обеих строк.
- Если первый символ в первой строке больше (или меньше), чем в другой строке, то первая строка больше (или меньше) второй. Были сделаны.
- В противном случае, если первые символы обеих строк совпадают, сравните вторые символы таким же образом.
- Повторяйте до конца любой строки.
- Если обе строки имеют одинаковую длину, они равны. В противном случае более длинная строка больше.
Сравнить две буквы в JavaScript - значит сравнить их коды в Unicode (16-битный формат преобразования Unicode). Итак, используя Unicode, мы знаем, что a
имеет feff0061
символьный код, b
имеет feff0062
и так далее.
'a'.charCodeAt().toString(16) -> 61 'b'.charCodeAt().toString(16) -> 62 ... 'z'.charCodeAt().toString(16) -> 7a
В этой задаче у нас есть новый алфавит order
, и нам нужно выяснить, как мы можем эффективно сравнить две буквы. Лучшая структура данных в этом случае - HashMap. Ключ будет буквой, а значение будет индексом, так как нам нужно сравнить две буквы, и большая будет буква с более высоким индексом.
Итак, после того, как мы все это поняли, мы можем перейти к алгоритму. Мы можем перебрать все слова и сравнить два слова (current
и next
) в каждой итерации буква за буквой. Алгоритм сравнения довольно прост:
- Если
current[i] === next[i]
нужно идти дальше. - Если
map[current[i]] < map[next[i]]
, нам нужно вернутьfalse
, потому что нам больше не нужно сравнивать другие символы. - Если
map[current[i]] > map[next[i]]
нам нужно перейти к следующей паре слов, если она существует.
Давайте посмотрим на реализацию:
Временная сложность равна O(mn)
, где m
- количество слов, а n
- средняя длина этих слов. В соответствии с ограничениями мы можем сказать, что временная сложность линейна, потому что в слове может быть не более 20 символов. Сложность пространства постоянна, потому что у нас не более 26 букв в order
.
Надеюсь, это было вам полезно. Спасибо за прочтение! Жду ваших отзывов. До скорой встречи ✌️