Описание

Удивительно, но на чужом языке они также используют строчные английские буквы, но, возможно, в другом 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:

  1. Сравните первый символ обеих строк.
  2. Если первый символ в первой строке больше (или меньше), чем в другой строке, то первая строка больше (или меньше) второй. Были сделаны.
  3. В противном случае, если первые символы обеих строк совпадают, сравните вторые символы таким же образом.
  4. Повторяйте до конца любой строки.
  5. Если обе строки имеют одинаковую длину, они равны. В противном случае более длинная строка больше.

Сравнить две буквы в 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.

Надеюсь, это было вам полезно. Спасибо за прочтение! Жду ваших отзывов. До скорой встречи ✌️