Описание испытания

Напишите функцию, которая находит самую длинную строку общего префикса среди массива строк.

Если общего префикса нет, вернуть пустую строку "".

Пример 1

Input: strs = ["flower","flow","flight"]
Output: "fl"

Пример 2

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Подход

Этот код используется для поиска самого длинного общего префикса массива строк, который определяется как самая длинная строка, являющаяся префиксом всех строк в массиве. Сортируя массив, а затем сравнивая первый и последний элементы, код может найти общий префикс, который будет общим для всех строк в массиве.

  1. Отсортируйте элементы массива строк с именем «strs» в лексикографическом (алфавитном) порядке с помощью метода Arrays.sort(strs).
  2. Присвойте первый элемент отсортированного массива (лексикографически наименьшую строку) строковой переменной s1.
  3. Присвойте последний элемент отсортированного массива (самую большую лексикографически строку) строковой переменной s2.
  4. Инициализировать целочисленную переменную idx значением 0.
  5. Запустите цикл while, который продолжается, пока idx меньше длины s1 и s2.
  6. В цикле while проверьте, равен ли символ с текущим индексом в s1 символу с тем же индексом в s2. Если символы равны, увеличьте значение idx на 1.
  7. Если символы не равны, выйдите из цикла while.
  8. Возвращает подстроку s1, которая начинается с первого символа и заканчивается idx-м символом (не включая).

Сложность

  • Временная сложность:
  1. Сортировка массива строк занимает время O(Nlog(N)). Это связано с тем, что большинство распространенных алгоритмов сортировки, таких как быстрая сортировка, сортировка слиянием и пирамидальная сортировка, имеют среднюю временную сложность O(Nlog(N)).
  2. Перебор символов первой и последней строк занимает время O(M). Это связано с тем, что код сравнивает символы двух строк, пока не найдет первое несоответствие.

Следовательно, общая временная сложность равна O(Nlog(N) + M).

  • Сложность пространства:
    пространство, используемое двумя строковыми переменными s1 и s2, пропорционально длине самой длинной строки в массиве. Следовательно, пространственная сложность равна O(1), так как она не зависит от размера входного массива.

Причина сортировки

Причина, по которой мы сортируем входной массив строк и сравниваем первую и последнюю строки, заключается в том, что самый длинный общий префикс всех строк должен быть префиксом первой строки и префиксом последней строки в отсортированном массиве. Это связано с тем, что строки упорядочены в соответствии с их алфавитным порядком (лексикографическим порядком).
Например, рассмотрим входной массив строк {"цветок", "поток", "полет"}. После сортировки массива получаем {"полет", "поток", "цветок"}. Самый длинный общий префикс всех строк — «fl», который находится в начале первой строки «flight» и второй строки «flow». Поэтому, сравнивая первую и последнюю строки отсортированного массива, мы можем легко найти самый длинный общий префикс.

function longestCommonPrefix(strs: string[]): string {
  strs.sort();
  const s1 = strs[0];
  const s2 = strs[strs.length - 1];
  let idx = 0;

  while (idx < s1.length && idx < s2.length) {
    if (s1.charAt(idx) === s2.charAt(idx)) {
      idx++;
    } else {
      break;
    }
  }

  return s1.substring(0, idx);
}